10.2 An NP-Complete Problem 426

10.2.1 The Satisfiability Problem 426

1. 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:

2. x and (y or not x) and (z or not y) = true

   ---

   1. 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.
   2. When applied to not(E) failing to find a solution means that E is always true.
   3. So SAT can be used to test for tautologies.

   ---

   DO Exercise 10.2.1 before continuing.

   10.2.2 Representing SAT Instances 427

   ---

   1. Rename the variables as x1...
   2. 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
3. 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

4. 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.

   ---

   1. Prove that there is a NTM that solves SAT in polynomial time -- it just guesses any satisfying assignment and checks it.
   2. Starting with any NP problem we prove that there is a SAT problem that expresses it.

      ---

      1. 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.
      2. We can rewrite the TM so that it never writes a Blank and never moves to theleft of the start position.
      3. So the TM won't need to visit more than p(n) symbols.
      4. Next note that we can encode the ID as a string with no more than p(n)+1 steps.
      5. This code can be modelled by a slew of boolean variables ( (p(n)+1)^2 ??).
      6. It is then easy to encode the starting and finishing states using the boolean variable.
      7. Coding the transitions is harder but possible.
      8. 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

10.3 A Restricted Satisfiability Problem 435

Exercise -- definitions

Define

1. Literal
2. Clause
3. CNF
4. k-CNF
5. CSAT
6. KSAT
7. 3SAT



Box -- reject bad syntax

10.3.1 Normal Forms for Boolean Expressions 436

Ch 10.3 pp -- Disjunctive Normal Form

It seems as though being able to determine the disjunctive normal form for a boolean function would trivially solve the SAT problem. Does this mean that determining the disjunctive normal form for a boolean expression is NP complete?

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.

10.3.2 Converting Expressions to CNF 437

Ch 10.3.2 pp 438 -- Intractable Problems

Could you please explain Theorem 10.12 I had trouble understanding the proof.

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

Take notes on the way that new variables are introduced in this proof.

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

Why is E not equivalent to F in general if S is an extension of T?

Equivalence can hold between expressions that use different variables:

1. 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
   Translate it into 3-CNF.

   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.

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

Next