.Open 15 . Schedule .Table Date .Item Meet'g .Item $Study(2 pts) .Item Bring(5 pts) .Item $Topic(5 pts) .Item Notes .Row Wed May 17 .Item 14 .Item Chapter 10 sections 10.1 .Item $Ex .Item Intractable Problems P & NP .Row Mon May 22 .Item 15 .Item Chapter 10 sections 10.2, 10.3 .Item $Ex .Item NP-Complete .Row Wed May 24 .Item 16 .Item Chapter 10 sections 10.4, 10.5 .Item $Ex .Item Graph Problems & TSP .Close.Table .Open 10 NP-Completeness .Open 10.2 An NP-Complete Problem 426 . 10.2.1 The Satisfiability Problem 426 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 .Box 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. .Close.Box . DO Exercise 10.2.1 before continuing. . 10.2.2 Representing SAT Instances 427 .Box Rename the variables as x1... Encode them using binary subscripts. .Close.Box . 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 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. .Box 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. .Box 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. .Close.Box .Close.Box . Corollary page 434 -- if SAT has a deterministic polynomial time solution then so has every NP problem. .Open 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 .Close .Close .Open 10.3 A Restricted Satisfiability Problem 435 . Exercise -- definitions Define .List Literal Clause CNF k-CNF CSAT KSAT 3SAT .Close.List . 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 .See http://ftp.csci.csusb.edu/dick/maths/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 (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 .Set *a) xy+xbar z b) wxyz+u+v c) wxy + xbar u v .Close.Set 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: .Set *a) xy+xbar z b) wxyz+u+v c) wxy_xbar u v .Close.Set Translate it into 3-CNF. .Open 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. .Close .Close .Close 15 . Next .See ./16.html . Notes (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. GJ75::=http://www.csci.csusb.edu/dick/cs546/14.html#GJ75. .Close