Complexity Theory Explained: Cook-Levin Theorem and NP-Completeness
Unravel the intricate concepts of complexity theory as we delve into the Cook-Levin Theorem, NP-completeness, 3-SAT problems, and the NP-hardness of CLIQUE. Understand how chaining reductions from 3-SAT to CLIQUE provide insights into proving NP-completeness. Follow a detailed proof that connects 3-SAT to CLIQUE through a clever reduction approach in this comprehensive exploration of 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
CMSC 28100 Introduction to Complexity Theory Complexity Theory Spring 2025 Instructor: William Hoza 1
?-CNF formulas Recall: A CNF formula is an AND of ORs of literals Definition: A ?-CNF formula is a CNF formula in which every clause has at most ? literals Example of a 3-CNF formula with two clauses: ? = ?1 ?2 ?6 ?5 ?1 ?2 2
The Cook-Levin Theorem Define ?-SAT = { ? ? is a satisfiable ?-CNF formula} The Cook-Levin Theorem: 3-SAT is NP-complete 3
NP-hard CIRCUIT-SAT 3-SAT NP-complete NP P 4
Chaining reductions together 3-SAT is the starting point for many NP-hardness proofs We are finally ready to prove that CLIQUE is NP-complete 5
CLIQUE is NP-complete Recall CLIQUE = ?,? ? contains a ?-clique Theorem: CLIQUE is NP-complete Proof: We showed CLIQUE NP in a previous class To prove that CLIQUE is NP-hard, we will do a reduction from 3-SAT 6
Proof that 3-SAT PCLIQUE Let ? be a 3-CNF formula (an instance of 3-SAT) Reduction: Given ? , produce ?,? ? is the number of clauses in ? ? is a graph on 3? vertices defined as follows 7
Reduction from 3-SAT to CLIQUE E.g., ? = ?1 ?2 ?5 ?1 ?4 ?6 For each clause 1 2 3, create a ?2 ?4 ?3 ?3 ?6 ?1 group of three vertices labeled 1, 2, 3 ?1 ?2 ?5 (If the clause only has one or two literals, ?1 ?2 then only use one or two vertices) ?4 Put an edge {?,?} if ? and ? are in ?4 ?6 different groups and ? and ? do not ?3 have contradictory labels (?? and ??) ?3 ?6 ?1 8
?1 ?2 ?5 YES maps to YES ?1 ?2 ?4 ?4 Suppose there exists ? such that ? ? = 1 ?6 ?3 ?3 ?6 ?1 In each clause, at least one literal is satisfied by ? Therefore, in each group, at least one vertex is satisfied by ?, i.e., it is labeled by a literal that is satisfied by ? Let ? be a set consisting of one satisfied vertex from each group Then ? is a ?-clique (vertices in ? cannot have contradictory labels) 9
?1 ?2 ?5 NO maps to NO ?1 ?2 ?4 ?4 ?6 ?3 Suppose ? has a ?-clique ? ?3 ?6 ?1 Let ? be an assignment that satisfies each vertex in ? This exists because no two vertices in ? have contradictory labels ? cannot contain two vertices from a single group, and ? = ?, so ? must contain one vertex from each group Therefore, ? satisfies at least one literal in each clause, so ? ? = 1 10
?1 ?2 ?5 Poly-time computable ?1 ?2 ?4 ?4 ?6 ?3 Hopefully it is clear that given ? , one can ?3 ?6 ?1 construct ?,? in polynomial time 11
NP-hard CIRCUIT-SAT CLIQUE NP-complete 3-SAT NP P 12
The subset sum problem ?1, ,??,? ?1, ,??,? and there exists ? 1, ,? such that ? ???= ? SUBSET-SUM = Theorem: SUBSET-SUM is NP-complete Proof: SUBSET-SUM NP. (Why?) We will prove it is NP-hard by reduction from 3-SAT 13
Proof that 3-SAT ?SUBSET-SUM Given ? with variables ?1, ,?? and clauses ?1, ,??, the reduction produces: ?1 ?2 ?? ?1 ?2 ?? Does ?2 appear in ?2? Suppose ? ? = 1 ??1= ? ?1= ??2= ? ?2= ???= ? ??= 1 1 0 0 1 1 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 0 1 0 0 0 0 1 1 If ??= 1, select ??? If ??= 0, select ? ?? Does ?? appear in ??? If only two literals in ?? are satisfied, select ??? Integers represented in base 8 ??1= ??1 ??2= ??2 ???= ??? 1 1 0 0 1 1 0 0 0 0 1 1 If only one literal in ?? is = satisfied, select ??? and ??? = Selected numbers sum to ? = ? = 1 1 1 3 3 3 3 14
Proof that 3-SAT ?SUBSET-SUM Given ? with variables ?1, ,?? and clauses ?1, ,??, the reduction produces: ?1 ?2 ?? ?1 ?2 ?? Does ?2 appear in ?2? Suppose a subset of the ??1= ? ?1= ??2= ? ?2= ???= ? ??= 1 1 0 0 1 1 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 0 1 0 0 0 0 1 1 numbers sum to ? There are no carries, because Does ?? appear in ??? each column has at most five ones Integers represented in base 8 If ??? is selected, set ??= 1 ??1= ??1 ??2= ??2 ???= ??? 1 1 0 0 1 1 0 0 0 0 1 1 = If ? ?? is selected, set ??= 0 = Each clause must have at least one satisfied literal = ? = 1 1 1 3 3 3 3 15
Proof that 3-SAT ?SUBSET-SUM Given ? with variables ?1, ,?? and clauses ?1, ,??, the reduction produces: ?1 ?2 ?? ?1 ?2 ?? Does ?2 appear in ?2? Reduction can be ??1= ? ?1= ??2= ? ?2= ???= ? ??= 1 1 0 0 1 1 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 0 1 0 0 0 0 1 1 performed in polynomial time Does ?? appear in ??? Integers represented in base 8 ??1= ??1 ??2= ??2 ???= ??? 1 1 0 0 1 1 0 0 0 0 1 1 = = = ? = 1 1 1 3 3 3 3 16
NP-hard CIRCUIT-SAT CLIQUE NP-complete 3-SAT SUBSET-SUM NP P 17
Hamiltonian paths Let ? be a directed graph Definition: A Hamiltonian path is a directed path that visits every vertex exactly once 18
DIRECTED-HAM-PATH is NP-complete Let DIRECTED-HAM-PATH = { ?,?,? ? is a digraph, ? and ? are vertices, and there exists a Hamiltonian path from ? to ?} Theorem: DIRECTED-HAM-PATH is NP-complete Proof: First, note DIRECTED-HAM-PATH NP. (Why?) To show NP-hardness, we will do a reduction from 3-SAT 19
Proof that 3-SAT PDIRECTED-HAM-PATH ? Let ? = ?1 ?2 ?? be a ?1 ?1 3-CNF formula on variables ?2 ?1, ,? ?2 ?3 Reduction: Given ? , produce ?,?,? defined on this and ? ?? upcoming slides ? clause nodes variable gadgets 20
Proof that 3-SAT PDIRECTED-HAM-PATH Poly-time computable positive detour ??= (?? ?? ?? = ( ?? detour separators negative detour 6? 1 nodes inside diamond (enough for all possible detours)
Proof that 3-SAT PDIRECTED-HAM-PATH ? YES maps to YES: Let ? be a ?1 1 ?1 satisfying assignment to ? ?2 ?2 0 Depending on assignment to ??, we ?3 zig-zag or zag-zig through ?? diamond 1 ? ?? Each clause has a satisfied literal; ? insert the corresponding detour 22
Proof that 3-SAT PDIRECTED-HAM-PATH ? NO maps to NO: Consider any ?1 1 ?1 Hamiltonian path from ? to ? ?2 ?2 0 Assign value to ?? based on edge ?3 traversed from top of ?? diamond 1 ? We must show that this assignment ?? satisfies every clause ? 23
Proof that 3-SAT PDIRECTED-HAM-PATH Consider any clause node ??. Path visits ?? from ?? some ?? diamond. WLOG, ??= (?? ) Claim: The path goes from?? back to that same diamond (??) ? ? ? Proof: The path must enter ? from the left. Therefore, the path must exit ? to the right. Therefore, the path must exit ? to the right, so the path must enter ? from ??
Proof that 3-SAT PDIRECTED-HAM-PATH ? Consequence: If we traverse a TRUE ?1 ?1 edge, then we can only take positive ?2 ?2 detours in that diamond ?3 If we traverse a FALSE edge, then we can only take negative detours in ? ?? that diamond ? Therefore, every clause is satisfied 25
