Cook-Levin Theorem: Understanding NP-Completeness
Explore the Cook-Levin Theorem in the context of NP-Completeness, delving into historical perspectives and mathematical significance. Learn about the complexity of 3SAT and its implications. Discover the key elements of the theorem and its proofs.
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
CS 121: Lecture 20 Cook-Levin Theorem Madhu Sudan https://madhu.seas.Harvard.edu/courses/Fall2020 Book: https://introtcs.org { The whole staff (faster response): CS 121 Piazza How to contact us Only the course heads (slower): cs121.fall2020.course.heads@gmail.com
Announcements: Advanced section Thursday: Nicole Immorlica on EconCS Midterm 2 in 1 week. Open book (Barak only). 2 pages cheat sheet (no collaboration). 90 minutes long. (70 if handwritten.) Homework 5 due Thursday.
Where we are: Part I: Circuits: Finite computation, quantitative study Part II: Automata: Infinite restricted computation, quantitative study Part III: Turing Machines: Infinite computation, qualitative study Part IV: Efficient Computation: Infinite computation, quantitative study Part V: Randomized computation: Extending studies to non-classical algorithms
Review of last lecture Defined NP (solutions/witnesses/proofs polytime verifiable) ?: 0,1 0,1 \NP ?? polytime comp.?.?.? ? = 1 ? ?.?.???,? = 1 Defined NP-Hard and NP-complete ? NP-hard ? NP,? ?? ? NP-complete ? NP and ? NP-complete. Asserted: 3SAT is NP-Complete 3SAT ?1 ?2 ?? = 1 ?1, ,?? 0,1 ?.?. ? literal in ?? that is 1. Will prove today Proved: ISET is NP-Complete (assuming assertion)
Today Cook-Levin Theorem: 3SAT is NP-Complete
NP-Completeness historically Many mathematicians sensed NP-hardness: Gauss (1800s): Can you factor integers? Godel (1956): Can you automate proving of theorems? Edmonds (1967): Travelling Salesperson has no polynomial time algorithm? If [3??? has ?(?2) time algorithm] then in spite of the undecidability of the Entscheidungsproblem, the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine Kurt G del to John von-Neumann, 1956
Todays Theorem 3??? is ??-hard. ??-hard + in ?? = ?? complete Cook Levin Theorem: ? ??? ?3??? Proof: Define ???????,3???? Lemma 1: ? ??, ? ???????? Lemma 2: ??????? ?3???? Lemma 3: 3???? ?3???
3NAND Input: is AND of constraints of form ??= ????(??,??) Output: 1 iff there is assignment ? {0,1}? satisfying Q: If = (?0= ????(?2,?3) ) (?3= ????(?2,?1) ) (?1= ????(?2,?3) ) what is 3NAND ? Lemma 2: ??????? ?3????
Lemma 3: 3???? ?3??? Key claim: For every ?,?,? {0,1}, ? ? ? ? = ????(?,?) ? ? ? ? Q: Prove key claim. Key claim lemma.
NANDSAT Input: NAND-CIRC program ? (aka circuit with NAND gates) Output: 1 iff there is ? {0,1}? s.t. ? ? = 1 Q: What is ???????( )?
Input: is AND of constraints of form ??= ????(??,??) Output: 1 iff there is assignment ? {0,1}? satisfying Lemma 2: ??????? ?3???? Proof by example: ?2= ????(?0,?1) ?0 ?3 ?3= ????(?0,?2) ?2 ?5 ?4= ????(?1,?2) ?5= ????(?3,?4) ?4 ?1 ?6= ????(?0,?0) ?5= ????(?0,?6) ?5= 1
Input: NAND-CIRC program ? (aka circuit with NAND gates) Output: 1 iff there is ? {0,1}? s.t. ? ? = 1 Lemma 1: For every ? ??, ? ???????? Proof: If ? ?? we know poly-time TM ?? s.t. ? {0,1}? ?? steps ? ? ?? ? {0,1}?? ? ? = 1 1 ?? ?
Input: NAND-CIRC program ? (aka circuit with NAND gates) Output: 1 iff there is ? {0,1}? s.t. ? ? = 1 Lemma 1: For every ? ??, ? ???????? Proof: If ? ?? we know poly-time TM ? s.t. ? {0,1}? By proof of ? ?/???? (Time SIZE) can find ?2? sized circuit ? s.t. ?2? gates ?? steps ? ? ? ? = ? ?? ?? ?? ? ?
Input: NAND-CIRC program ? (aka circuit with NAND gates) Output: 1 iff there is ? {0,1}? s.t. ? ? = 1 Lemma 1: For every ? ??, ? ???????? Proof: If ? ?? we know poly-time TM ?? s.t. ? {0,1}? By proof of ? ?/???? can find ?2? sized circuit ? s.t. ?2? gates ? ? ? ? {0,1}?? ? ? = 1 1 ?? ?
Input: NAND-CIRC program ? (aka circuit with NAND gates) Output: 1 iff there is ? {0,1}? s.t. ? ? = 1 Lemma 1: For every ? ??, ? ???????? Proof: If ? ?? we know poly-time TM ? s.t. ? {0,1}? By proof of ? ?/???? can find ?2? sized circuit ? s.t. ?2? gates ? ? ? {0,1}?? ? ? = 1 1 ?? ?
Example to illustrate proof Example: ???? ?3??? Input: Graph ? integer ? Step 1: NAND circuit ?? such that ??? = 1 iff ? ? and ? independent in ? Step 2: 3NAND formula s.t. ? with ? = 1 iff ? s.t. ??? = 1 Step 3: 3CNF formula ? s.t. ? ? = (?) for every ?
Next lecture More reductions. See more diverse NP-complete problems.
