NP-Completeness and Cook-Levin Theorem
Explore the concepts of NP-completeness, Cook-Levin Theorem, and constructing tableaus for non-deterministic Turing Machines. Learn about NP-complete languages, polynomial-time reductions, and the significance of NP-completeness in computational complexity theory.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
18.404/6.840 Lecture 16 Last time: - NP-completeness - 3??? P?????? - 3??? P ??????? Today: (Sipser 7.4) - Cook-Levin Theorem: ??? is NP-complete - 3??? is NP-complete
Quick Review Defn: ? is NP-complete if 1) ? NP 2) For all ? NP, ? P? Check-in 16.1 today NP If ? is NP-complete and ? P then P = NP. The big sigma notation means summing over some set. P??? P3??? P?????? P??????- -??? P??????? P???????? previously ? = 1 + 2 + + ? Importance of NP-completeness 1) Evidence of computational intractability. 2) Gives a good candidate for proving P NP. 1 ? ? recitation The big AND (or OR) notation has a similar meaning. For example, if ? = ?1 ?? and ? = ?1 ?? are two strings of length ?, when does the following hold? NP To show some language ? is NP-complete, show 3??? P?. or some other previously shown NP-complete language P NP-complete = TRUE ??= ?? 1 ? ? (a) Whenever ? and ? agree on some symbol. (b) Whenever ? = ?. Or: P = NP Check-in 16.1
Cook-Levin Theorem (idea) Theorem: ??? is NP-complete Proof: 1) ??? ?? (done) 2) Show that for each ? ?? we have ? ????: Let ? ?? be decided by NTM ? in time ??. Give a polynomial-time reduction ? mapping ? to ???. ?: formulas ? ? = ??,? ? ? iff ??,? is satisfiable Idea: ??,? simulates ? on ?. Design ??,?to say ? accepts ?. Satisfying assignment to ??,? is a computation history for ? on ?.
Tableau for ? on ? Defn: An (accepting) tableau for NTM ? on ? is an ?? ?? table representing an computation history for ? on ? on an accepting branch of the nondeterministic computation. ?? ?0?1?2?3 ?? a ?7?2 Start configuration for ? on ? Construct??,? to say ? accepts ?. ??,? says a tableau for ? on ? exists. ?? ??,?= ?cell ?start ?move ?accept ?accept Accepting configuration
Constructing ??,?: ?cell ? ?0?1?2?3 ?? ?7?2 a a ?7 a ?7 ?,? a ?7 a ?7 ? ??,? says a tableau for ? on ? exists. ??,?= ?cell ?start ?move ?accept Check-in 16.2 How many variables does ??,? have? Recall that ? = |?|. (a) ?(?) (b) ?(?2) (c) ?(??) (d) ?(?2?) ?7 a b ?accept Cell ?,? can contain any symbol in ? ?cell says exactly one light is on per cell i.e., exactly one ??,?,?= TRUE for each ?,? . lights represent ??,?,? ??,?,a = TRUE ??,?, = TRUE ??,?,?7= TRUE In every cell at least one light and at most one light ??,?,?1 ??,?,?2 ??,?,?? The variables of ??,? are ??,?,? for 1 ?,? ?? and ? ?. ??,?,?= TRUE means cell ?,? contains ?. ??,?,? ??,?,? ?cell = ??,?,? 1 ?,? ?? ?,? ? ? ? ? ? Check-in 16.2
Constructing ??,?: ?start and ?accept ?? ?? 1 1 2 3 Start configuration ?0?1?2?3 ?? ?7?2 1 a ??,? says a tableau for ? on ? exists. ??,?= ?cell ?start ?move ?accept ?celldone ?? ?accept Accepting configuration ?start= ?1,1,?0 ?1,2,?1 ?1,3,?2 ?1,??, ?accept= ???,?,?accept 1 ? ??
Constructing ??,?: ?move ? ?0?1?2?3 ?? ?7?2 2 3 neighborhood a ? Legal neighborhoods: consistent with ? s transition function potential examples: a ?7 ?3 b a b c a b c a b c ?accept b ?5 a c a b c a d b c Illegal neighborhoods: not consistent with ? s transition function ??,? says a tableau for ? on ? exists. a ?7 a a ?7 ?3 a b c a b c c c examples: a ?2 d ?4 a d c c b c ??,?= ?cell ?start ?move ?accept Claim: If every 2 3 neighborhood is legal then tableau corresponds to a computation history. ??,? 1,r ??,?,s ??,?+1,t ??+1,? 1,v ??+1,?,y ??+1,?+1,z ?move = 1<?,?<?? Legal Says that the neighborhood at ?,? is legal r s t v y z
Conclusion: ??? is NP-complete ?? ?0?1?2?3 ?? a ?7?2 Summary: For ? NP, decided by NTM ?, we gave a reduction ? from ? to ???: ?: formulas ? ? = ??,? ? ? iff ??,? is satisfiable. ?? ?accept ??,?= ?cell ?start ?move ?accept The size of ??,? is roughly the size of the tableau for ? on ?, so size is ? ?? ??= ? ?2?. Therefore ? is computable in polynomial time.
3??? is NP-complete a b a b = c 1 1 1 0 1 1 1 0 1 a b a b = c 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 a b c a b c a b c a b c a b c a b c a b c a b c Theorem: 3??? is NP-complete Proof: Show ??? ?3??? Give reduction ? converting formula ? to 3CNF formula ? , preserving satisfiability. (Note: ? and ? are not logically equivalent) Example: Say ? = Tree structure for ?: a b c a b Logical equivalence: ? ? and ? ?? ? and ? ? ? = a b ?1 a b z1 a b z1 a b z1 ?4 ?1 c ?2 repeat for each ?? Check-in 16.3 If ? has ? operations ( and ), how many clauses has ? ? (a) ? + 1 (c) ?2 (b) 4? + 1 (d) 2?2 z1 c ?2 ?1 c ?2 z1 c z2 ?2 ?3 (?4) ?1 b a c Observe that a b c is logically equivalent to a b c a b c a b c a b c a b c a b Check-in 16.3
Quick review of today ???is NP-complete 1. 3??? is NP-complete 2.
