NP-completenessImportanceBoolean formulasThe SAT problemPolynomial time reducibilityThe 3SAT problemReducing 3SAT to CLIQUE (a)Reducing 3SAT to CLIQUE (b)Reducing 3SAT to CLIQUE (c)Reducing 3SAT to CLIQUE (d)Definition of NP-completenessCook-Levin theorem: Getting startedCook-Levin theorem: TableausCook-Levin theorem: Cook-Levin theorem: cellCook-Levin theorem: startCook-Levin theorem: acceptCook-Levin theorem: WindowsCook-Levin theorem: Examples of legal and illegal windowsCook-Levin theorem: Claim about windowsCook-Levin theorem: moveCook-Levin theorem: The complexity of the reductionCook-Levin theorem: Wrapping it upThe NP-completeness of 3SATNP-completenessNP-completenessSection 7.4 Giorgi Japaridze Theory of ComputabilityImportance 7.4.aGiorgi Japaridze Theory of ComputabilityNP-complete problems form a certain important subclass of NP. The phenomenon of NP-completeness was discovered in the early 1970s by Stephen Cook and Leonid Levin.• If a polynomial time algorithm exists for any of the NP-complete problems, all problems in NP would be polynomial time solvable. • To prove that P=NP, it would be sufficient to take any particularNP-complete problem A and show that AP. • To prove that P≠NP, it would be sufficient to take any particularNP-complete problem A and show that AP. • On the practical side, finding that a given problem A is NP-complete may prevent wasting time looking for a (probably nonexistent, or unlikely-to-be-found even if exists) polynomial time algorithm for A.Boolean formulas 7.4.bGiorgi Japaridze Theory of ComputabilityBoolean variables x,y,… take one of the two values 0 (false ) or 1 (true).Boolean operations:  (NOT),  (AND),  (OR). We write A for A.Boolean formulas are constructed from variables and operations in the standard way. Once a truth assignment for variables is given, the value of a compound formula is calculated as follows: 0 = 1 0  0 = 0 0  0 = 01 = 0 0  1 = 0 0  1 = 1 1  0 = 0 1  0 = 1 1  1 = 1 1  1 = 1If x=0 and y=1, what is the value of the following formula?(y  (x  y))  (x  y) (1  (0  1))  (0  1)(1  (1  0))  (0  0)(1  1 )  0 1  0 1The SAT problem 7.4.cGiorgi Japaridze Theory of ComputabilityWe say that a Boolean formula is satisfiable iff there is an assignment of 0s and 1s to its variables that makes the formula evaluate to 1. Are the following formulas satisfiable?x(xy)x(xy)SAT = {<> |  is a satisfiable Boolean formula}SAT  P?SAT  NP?Polynomial time reducibility 7.4.dGiorgi Japaridze Theory of ComputabilityDefinition 7.28 A polynomial time computable function is a function computed by some polynomial time TMO.Definition 7.29 Let A and B be be languages over an alphabet . We say that A is polynomial time mapping reducible, or simply polynomial time reducible, to B, written APB, if a polynomial time computable function f: *  * exists s.t. for every string w*, wA iff f(w)B.Such a function f is called a polynomial time reduction of A to B.Theorem 7.31 If APB and BP, then AP. Proof. Assume M is a polynomial time decider for B, and f is apolynomial time reduction from A to B. The following is a polynomial time algorithm deciding A: N = “On input w: 1. Compute f(w). 2. Run M on input f(w) and do (accept or reject) whatever M does.”The 3SAT problem 7.4.eGiorgi Japaridze Theory of Computability• A literal is a Boolean variable x or a negated Boolean variable x.• A clause is several literals connected with s, as in (x  y  z  t).• A Boolean formula is in conjunctive normal form, called a cnf-formula, if it comprises several clauses connected with s, as in (x  y  z  t)  (x  z)  (x  y t) • A cnf-formula is a 3cnf-formula if all the clauses have 3 literals, as in (x  y  z)  (x  z  t)  (x  y  t)  (z  y  t)• 3SAT = {<> |  is a satisfiable 3cnf-formula} 3SAT  P?3SAT  NP?Reducing 3SAT to CLIQUE (a) 7.4.fGiorgi Japaridze Theory of ComputabilityTheorem 7.32 3SAT is polynomial time reducible to CLIQUE. Proof. Let  be a 3cnf-formula with k clauses such as  = (a1 b1 c1)  (a2 b2 c2)  …  (ak bk ck)Our reduction f is going to generate the string <G,k>, where G is an undirected graph defined as follows. The nodes of G are organized into k groups of three nodes each calledthe triples, t1,…,tk. Each triple corresponds to one of the clauses in, and each node in a triple corresponds to a literal in the associated clause. Label each node of G with its corresponding literal in .The edges of G connect all but two types of pairs of nodes: (1) no edge is present between two nodes in the same triple, and (2) No edge is present between nodes with contradictory labels,as in x and x.Reducing 3SAT to CLIQUE (b) 7.4.gGiorgi Japaridze Theory of Computability  = (x  x  z)  (x  z  z)  (x  z  z)For instance, if  is as above, then G would bexzzzzxzxxObviously transforming  into G takes polynomial time. Next we argue that (slide 7.4.h) if 3SAT, then <G,k>CLIQUE, and that (slide 7.4.i) if <G,k>CLIQUE, then 3SAT. So, we indeed have a polynomial time reduction.Reducing 3SAT to CLIQUE (c) 7.4.hGiorgi Japaridze Theory of Computabilityxzzzzxzxx  = (x  x  z)  (x  z  z)  (x  z  z)Suppose  has a satisfying assignment. Then at least one literal should be true in each clause. Select one such literal in each clause, and select the corresponding nodes in the graph. Those nodes form a k-clique! Because there are k such nodes, and each pairis connected by an edge because they are in different triples and non-contradictory.Reducing 3SAT to CLIQUE (d) 7.4.iGiorgi Japaridze Theory of Computabilityxzzzzxzxx  = (x  x  z)  (x  z  z)  (x  z  z)Now suppose G has a k-clique. Each of its nodes should be in different triples as thereare no edges within triples. So, each triple has exactly one node of the clique. Selectthe corresponding literals in , and select an assignment that makes each such literaltrue. This