Exercise -- definitions
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:
- x+y is not equivalent to x
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:
Translate it into 3-CNF.
- *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.