>> [CNS] >> [Comp Sci Dept] >> [R J Botting] >> [CS546/646] >> 15 [Text Version]

[About] [Contact] [Grades] [Projects] [Submit] [Schedule] [Syllabus] [Search

Session: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14]

Thu Jun 8 13:03:00 PDT 2006

- 15
- : Schedule
- : 10 NP-Completeness
- : : 10.2 An NP-Complete Problem 426
- : : : 10.2.1 The Satisfiability Problem 426
- : : : DO Exercise 10.2.1 before continuing.
- : : : 10.2.2 Representing SAT Instances 427
- : : : 10.2.3 NP-Completeness of the SAT Problem 428
- : : : Theorem 10.9 Cook's Theorem
- : : : Error on page 430 and 434 from web site
- : : : Ch 10.2.3 pp 428-434 -- SAT Problem encodes NTM
- : : : Ch 10.2 pp 428 -- SAT NP-complete
- : : : Class Exercise
- : : : Corollary page 434 -- if SAT has a deterministic polynomial time solution then so has every NP problem.
- : : : 10.2.4 Exercises for Section 10.2 434
- : : : : Exercise 10.2.1 Boolean Expressions
- : : : : ! Exercise 10.2.2 four node graphs
- : : 10.3 A Restricted Satisfiability Problem 435
- : : : Exercise -- definitions
- : : : Box -- reject bad syntax
- : : : 10.3.1 Normal Forms for Boolean Expressions 436
- : : : Ch 10.3 pp -- Disjunctive Normal Form
- : : : 10.3.2 Converting Expressions to CNF 437
- : : : Ch 10.3.2 pp 438 -- Intractable Problems
- : : : Theorem 10.12 Moving negation down to literals
- : : : 10.3.3 NP-Completeness of CSAT 440
- : : : Theorem 10.13 Can reduce SAT to 3SAT in polynomial time
- : : : Ch 10.3 pp 435-440 -- 3SAT Reduction
- : : : What is the significance between SAT and CSAT?
- : : : Ch 10.3.2 pp 438 -- Converting Expressions to CNF
- : : : Ch 10.3.3 pp 440 -- NP-Completeness of CSAT
- : : : Ch 10.3.3 pp 440-443 -- NP-completeness of CSAT
- : : : DO first part of Exercise 10.3.1 before continuing
- : : : Ch 10, ch10 pp 445 -- CNF to 3-CNF
- : : : 10.3.4 NP-Completeness of 3SAT 445
- : : : Theorem 10.15 Can reduce CSAT to 3SAT...
- : : : Ch 10 pp 429 -- SAT and 3SAT
- : : : COMPLETE exercise 10.3.1 before continuing
- : : : 10.3.5 Exercises for Section 10.3 446
- : : : : Exercise 10.3.1 is best done in pieces: BE->CNF->3CNF as above
- : : : : Exercise 10.3.2 4TA-SAT
- : : : : Error in Exercise 10.3.3 from web sight
- : : : : Exercise 20.3.4 2SAT is in P
- : Next
- : Notes
- Standard Definitions
- From Logic

- SAT::problem=
*Can this Boolean Expression be true*.This is the canonical NP_complete problem.

It is also the first problem ever proved to be NP-Complete.

In a sense SAT is about solving an equation:

- x and (y or not x) and (z or not y) = true
- If we have a good SAT algorithm then we can use it on
*not( E )*and it will find a solution iff E is false for some set of values for its variables. - When applied to
*not(E)*failing to find a solution means that E is always true. - So SAT can be used to test for tautologies.

#### DO Exercise 10.2.1 before continuing.

#### 10.2.2 Representing SAT Instances 427

- Rename the variables as x1...
- Encode them using binary subscripts.

#### 10.2.3 NP-Completeness of the SAT Problem 428

You might say that this theorem came from trying to find a way to code efficient*ND*solution as efficient deterministic solutions. However we end up failing. Instead we discover that SAT is as hard as any other NP problem.#### Theorem 10.9 Cook's Theorem

#### Error on page 430 and 434 from web site

There is a condition*U*(Uniqueness) missing. It says (roughly) that for i,j there is only one Z such that y[i,j,Z]. It would look like - If we have a good SAT algorithm then we can use it on
- AND[i,j,W,Z]( NOT( y[i,j,W] AND y[i,j,Z] ).
This takes polynomial time to express and is polynomial in length.
On page 434 we have

- E[M,w] = S ^ N ^ F ^ U.
#### Ch 10.2.3 pp 428-434 -- SAT Problem encodes NTM

Could you please show a small example of how a boolean expression can be transformed into IDs like in 10.2.3?We transform Boolean Expressions into Turing data in 10.2.2 above! !0.2.3 is about writing a Boolean expression that represents the complete operation of a TM from Start to Finish. Perhaps the simplest possible one would be a machine with to states q0 and qf which, on any data, moves to the right leaving the symbol alone and enters qf (and halts). More in class...

#### Ch 10.2 pp 428 -- SAT NP-complete

After reading I am still not sure why SAT is NP-complete can you please go over why SAT is NP-complete.#### Class Exercise

You need to be able to express the idea of the proof as simple but clear paragraph of about 250(?) words. However, in the final, I do not expect you to reproduce all the details of what is going on.- Prove that there is a NTM that solves SAT in polynomial time -- it just guesses any satisfying assignment and checks it.
- Starting with any NP problem we prove that there is a SAT problem that expresses it.
- First note that we have a NTM that halts and solves the problem in p(n) steps for some polynomial of the length of the input.
- We can rewrite the TM so that it never writes a Blank and never moves to theleft of the start position.
- So the TM won't need to visit more than p(n) symbols.
- Next note that we can encode the ID as a string with no more than p(n)+1 steps.
- This code can be modelled by a slew of boolean variables ( (p(n)+1)^2 ??).
- It is then easy to encode the starting and finishing states using the boolean variable.
- Coding the transitions is harder but possible.
- Adding a uniqueness coinstraint gives a large boolean expression that encodes the whole computation if and only if the expression is satisfied.

#### Corollary page 434 -- if SAT has a deterministic polynomial time solution then so has every NP problem.

#### 10.2.4 Exercises for Section 10.2 434

##### Exercise 10.2.1 Boolean Expressions

Try truth tables to count that satisfying truth assignments.##### ! Exercise 10.2.2 four node graphs

- Literal
- Clause
- CNF
- k-CNF
- CSAT
- KSAT
- 3SAT
- x+y is not equivalent to x
(By definition)
#### Ch 10.3.3 pp 440 -- NP-Completeness of CSAT

Can you explain the trick introduced in Theorem 10.13 used to prove CSAT is NP-Complete.Take note of the tricky use of extra variables!

#### Ch 10.3.3 pp 440-443 -- NP-completeness of CSAT

Is their an easier way to understand the Theorem 10.13 on page 440 then three pages of explanation.I haven't seen a better proof/explanation. Doing some examples should help convince us that any SAT can be reduced to a 3SAT.

#### DO first part of Exercise 10.3.1 before continuing

What is is the CNF encoding (using extra variables) of- *a) xy+xbar z
- b) wxyz+u+v
- c) wxy + xbar u v

Would you please go over the reduction of 3SAT to SAT? I have seen it twice and I am still a bit confused.

Actually we need to show that we can reduce SAT to 3SAT!. Because 3SAT is NP we can use Cook's theorem to show that 3SAT reduces to SAT.

#### Ch 10, ch10 pp 445 -- CNF to 3-CNF

Could you describe the steps that must be followed in order to convert a CNF expression into a 3-CNF expression? The objective of exercise 10.3.1 was to make such conversions, but I didn't quite understand how the book went about it.#### 10.3.4 NP-Completeness of 3SAT 445

#### Theorem 10.15 Can reduce CSAT to 3SAT...

#### Ch 10 pp 429 -- SAT and 3SAT

Could you explain the difference between SAT and 3SAT It seems that they are the same thing.#### COMPLETE exercise 10.3.1 before continuing

You have the CNF for the following Boolean Expressions:- *a) xy+xbar z
- b) wxyz+u+v
- c) wxy_xbar u v

#### 10.3.5 Exercises for Section 10.3 446

##### Exercise 10.3.1 is best done in pieces: BE->CNF->3CNF as above

##### Exercise 10.3.2 4TA-SAT

Look for a KISS trick reducing SAT to 4TA-SAT##### Error in Exercise 10.3.3 from web sight

Three missing integer variables i,j,k : 1..n.E[n] has clauses (x[i]+x[j]+x[j]) and (x_bar[i]+x_bar[j]+x_bar[k]).

##### Exercise 20.3.4 2SAT is in P

Try this for yourself for a time. No more than an hour and if then stuck search the web for "2SAT polynomial". I found a cool Power Point demo.... bring the URL in and demo it. - GJ75::= See http://www.csci.csusb.edu/dick/cs546/14.html#GJ75.
- FSA::="Finite State Acceptor/Automata", a theoretical machine with a finite set of states.
- ND::="Non-deterministic", a machine that can try out many possibilities
and always guesses the right choice. Note: For a given problem
a
*ND*solution is simpler and easier to understand than a deterministic one. We study*ND*machines to discover how to use them as high-level designs for more complicated deterministic machines. Plus it's fun. - PDA::="Push down Automata", a machine with a finite control and a
single stack for remembering intermediate data. Kind of like half a
*TM*. - RJB::=
*The author of this document*, [ ../index.html ] - |-
*RJB*="Richard J Botting, Comp Sci Dept, CSUSB". - Schedule::= See http://www.csci.csusb.edu/dick/cs546/schedule.html.
- Search::= See http://www.csci.csusb.edu/dick/cs546/lookup.php.
- Syllabus::= See http://www.csci.csusb.edu/dick/cs546/syllabus.html, and also see [ syllabus.html ] (my generic syllabus).
- TBA::="To Be Announced".
- TM::="Turing Machine".
- NTM::="Nondeterministic Turing Machine".
- nondeterministic::="A machine that can make choices as it runs and accepts an input iff any sequence of choices leads to acceptance."
- DTM::="Deterministic Turing Machine".
- runtime::=
*run_time*, - run_time::="The number of steps a TM takes before it halts when start on a given input".
- complexity::="The largest
*run_time*for any word with a given length" , usually expressed as an assymptotic (Big-O) formula. - P::@problem=
*class of problems that a*.*DTM*can compute in*polynomial_time* - NP::@problem=
*class of problems that a*.*NTM*can compute in*polynomial_time* - polynomial_time::=
*An algorithm/TM is said to halt in polynomial time if the number of steps given n items of data is less than O(n^c) for some constant c*.# From Logic

- LOGIC::= See http://www.csci.csusb.edu/dick/maths/logic_25_Proofs.html
- (LOGIC)|- (ei): Existential instantiation -- if P is true of something then we can
substitute a new variable for it.
- (LOGIC)|- (eg): existential generalization -- if P is true of this thing then
it is true of something!
- (LOGIC)|- (given): a proposition that is assumed as part of a Let...End Let argument.
Typically
*if A and B and C then D*starts with assuming A,B, and C are*given*. They are called the hypotheses. - (LOGIC)|- (goal): a proposition that we wish to prove. Typically the part after
the
*then*in an*if...then...*result. This is called the conclusion. - (LOGIC)|- (def): By definition of a term defined above.
- (LOGIC)|- (algebra): Either by using well known algebraic results, or by
use a series of algebraic steps.
- (LOGIC)|- (RAA): Reduce to absurdity. The end of a Let/Po/Case/Net that establishes the negation of the last set of assumptions/hypotheses.

Date | Meet'g | Study(2 pts)
| Bring(5 pts) | Topic(5 pts)
| Notes |
---|---|---|---|---|---|

Wed May 17 | 14 | Chapter 10 sections 10.1 | Ex
| Intractable Problems P & NP | |

Mon May 22 | 15 | Chapter 10 sections 10.2, 10.3 | Ex
| NP-Complete | |

Wed May 24 | 16 | Chapter 10 sections 10.4, 10.5 | Ex
| Graph Problems & TSP |

Since the disjunctive normal form lists the truth assignments and so solves SAT we can be sure that any mapping to disjunctive normal form will NOT take polynomial time. Notice that reducing to disjunctive normal form is not a problem in the technical sense so we can't say that it is NP-complete. However we can conclude that (if P!=NP) that the mapping must be expensive -- not polynomial.

By the way: there is a comparatively simple process for converting to disjunctive normal form [ logic_27_Tableaux.html ] -- but sometimes the tree grows wildly -- just as the theory of NP-completeness suggests.

Equivalence can hold between expressions that use different variables:

*. . . . . . . . . ( end of section 15) *<<Contents | End>>

(Ex): Do as many of the relevant exercises as you have time for. You may work in a team of up to 4 students and hand in one joint solution. Bring to class one written solution to an exercise. This must not be a solution to an exercise marked with an asterisk(*) to earn full credit. One of the authors will be invited to present the solution to the class -- failure will loose points. Students taking CS646 must hand in the solution to an exercise marked with an exclamation mark(!) to earn full credit.

(Study): Read & think about the assigned items. Submit one question by selecting the submit button at the top of the web page. To earn complete credit you need to do this at least 90 minutes before the start of class. Hints. Read each section twice -- once the easy bits and then the tough bits. Use a scratch pad and pencil as you read.

(Topic): To earn all the possible points you must: turn up on time, not leave early, present work when called upon, and take part in discussions.