WIXLIB

Correctness of Reductionϕ is satisfiable implies Gϕ is 3-colorableif xi is assigned True, color vi True and v̄i Falsefor each clause Cj (a b c) at least one of a, b, c iscolored True. OR-gadget for Cj can be 3-colored such thatoutput is True.Gϕ is 3-colorable implies ϕ is satisfiableif vi is colored True then set xi to be True, this is a legal truthassignmentconsider any clause Cj (a b c). it cannot be that alla, b, c are False. If so, output of OR-gadget for Cj has to becolored False but output is connected to Base and False!Chandra & Manoj (UIUC)CS37424Fall 201524 / 57

Graph generated in reduction. from 3SAT to 3COLORTFXaaChandra & Manoj (UIUC)bcbCS374cd25dFall 201525 / 57

Part IICircuit SATChandra & Manoj (UIUC)CS37426Fall 201526 / 57

CircuitsDefinitionA circuit is a directed acyclic graph with1Input vertices (withoutincoming edges) labelled with0, 1 or a distinct variable.2Every other vertex is labelled , or .3Single node output vertexwith no outgoing edges.Inputs: 1?0?Chandra & Manoj (UIUC)CS37427Fall 201527 / 57

CircuitsDefinitionA circuit is a directed acyclic graph with 1Input vertices (withoutincoming edges) labelled with0, 1 or a distinct variable. 2Every other vertex is labelled , or . 3Single node output vertexwith no outgoing edges.Inputs: 1?0?Chandra & Manoj (UIUC)CS37427Fall 201527 / 57

CircuitsDefinitionA circuit is a directed acyclic graph withOutput: 1Input vertices (withoutincoming edges) labelled with0, 1 or a distinct variable. 2Every other vertex is labelled , or . 3Single node output vertexwith no outgoing edges.Inputs: 1?0?Chandra & Manoj (UIUC)CS37427Fall 201527 / 57

CSAT: Circuit SatisfactionDefinition (Circuit Satisfaction (CSAT).)Given a circuit as input, is there an assignment to the input variablesthat causes the output to get value 1?Chandra & Manoj (UIUC)CS37428Fall 201528 / 57

CSAT: Circuit SatisfactionDefinition (Circuit Satisfaction (CSAT).)Given a circuit as input, is there an assignment to the input variablesthat causes the output to get value 1?ClaimCSAT is in NP.12Certificate: Assignment to input variables.Certifier: Evaluate the value of each gate in a topological sort ofDAG and check the output gate value.Chandra & Manoj (UIUC)CS37428Fall 201528 / 57

Circuit SAT vs SATCNF formulas are a rather restricted form of Boolean formulas.Circuits are a much more powerful (and hence easier) way to expressBoolean formulasChandra & Manoj (UIUC)CS37429Fall 201529 / 57

Circuit SAT vs SATCNF formulas are a rather restricted form of Boolean formulas.Circuits are a much more powerful (and hence easier) way to expressBoolean formulasHowever they are equivalent in terms of polynomial-time solvability.TheoremSAT P 3SAT P CSAT.TheoremCSAT P SAT P 3SAT.Chandra & Manoj (UIUC)CS37429Fall 201529 / 57

Converting a CNF formula into a CircuitGiven 3CNF formulat ϕ with n variables and m clauses, create aCircuit C .Inputs to C are the n boolean variables x1 , x2 , . . . , xnUse NOT gate to generate literal xi for each variable xiFor each clause ( 1 2 3 ) use two OR gates to mimicformulaCombine the outputs for the clauses using AND gates to obtainthe final outputChandra & Manoj (UIUC)CS37430Fall 201530 / 57

Example ϕ x1 x3 x4 x1 x2 x3 x2 x3 x4Chandra & Manoj (UIUC)CS37431Fall 201531 / 57

Converting a circuit into a CNF formulaLabel the nodesOutput:Output: , k 1 ? ?0 , f?1,aInputs , h , g?,b?,c?,e0,dInputs(A) Input circuitChandra & Manoj (UIUC) , j , i(B) Label the nodes.CS37432Fall 201532 / 57

Converting a circuit into a CNF formulaIntroduce a variable for each nodeOutput: , k1,axi , j , i , fOutput: , k?,bxf , h , g?,c0,d?,exa 1,aInputs , j , i , gxgxb ?,b xc?,c , fxj , hxd 0,dxhxe ?,eInputs(B) Label the nodes.Chandra & Manoj (UIUC)xk(C) Introduce var for each node.CS37433Fall 201533 / 57

Converting a circuit into a CNF formulaWrite a sub-formula for each variable that is true if the var is computed correctly.Output: , kxixfxa 1,axk , j , i , gxgxb ?,b xc?,c , fxj , hxd 0,dxhxe ?,eInputs(C) Introduce var for each node.Chandra & Manoj (UIUC)CS374xk (Demand a sat’ assignment!)xk xi xkxj xg xhxi xfxh xd xexg xb xcxf xa xbxd 0xa 1(D) Write a sub-formula foreach variable that is true if thevar is computed correctly.34Fall 201534 / 57

Converting a circuit into a CNF formulaConvert each sub-formula to an equivalent CNF formulaxkxk xi xjxj xg xhxi xfxh xd xexg xb xcxf xa xbxd 0xa 1Chandra & Manoj (UIUC)xk( xk xi ) ( xk xj ) (xk xi xj )( xj xg ) ( xj xh ) (xj xg xh )(xi xf ) ( xi xf )(xh xd ) (xh xe ) ( xh xd xe )(xg xb ) (xg xc ) ( xg xb xc )( xf xa ) ( xf xb ) (xf xa xb ) xdxaCS37435Fall 201535 / 57

Converting a circuit into a CNF formulaTake the conjunction of all the CNF sub-formulasOutput: , kxixfxa 1,axk , j , i , gxgxb ?,b xc?,c , fxj , hxd 0,dxhxe ?,eInputsxk ( xk xi ) ( xk xj ) (xk xi xj ) ( xj xg ) ( xj xh ) (xj xg xh ) (xi xf ) ( xi xf ) (xh xd ) (xh xe ) ( xh xd xe ) (xg xb ) (xg xc ) ( xg xb xc ) ( xf xa ) ( xf xb ) (xf xa xb ) ( xd ) xaWe got a CNF formula that is satisfiable if and only if the originalcircuit is satisfiable.Chandra & Manoj (UIUC)CS37436Fall 201536 / 57

Reduction: CSAT P SAT12For each gate (vertex) v in the circuit, create a variable xvCase : v is labeled and has one incoming edge from u (soxv xu ). In SAT formula generate, add clauses (xu xv ),( xu xv ). Observe thatxv xu is trueChandra & Manoj (UIUC) CS374(xu xv )both true.( xu xv )37Fall 201537 / 57

Reduction: CSAT P SATContinued.1Case : So xv xu xw . In SAT formula generated, addclauses (xv xu ), (xv xw ), and ( xv xu xw ). Again,observe that xv xu xwChandra & Manoj (UIUC) is trueCS374(xv xu ),(xv xw ),all true.( xv xu xw ) 38Fall 201538 / 57

Reduction: CSAT P SATContinued.1Case : So xv xu xw . In SAT formula generated, addclauses ( xv xu ), ( xv xw ), and (xv xu xw ).Again observe thatxv xu xw is trueChandra & Manoj (UIUC) CS374( xv xu ),( xv xw ),all true.(xv xu xw )39Fall 201539 / 57

Reduction: CSAT P SATContinued.12If v is an input gate with a fixed value then we do the following.If xv 1 add clause xv . If xv 0 add clause xvAdd the clause xv where v is the variable for the output gateChandra & Manoj (UIUC)CS37440Fall 201540 / 57

Correctness of ReductionNeed to show circuit C is satisfiable iff ϕC is satisfiable Consider a satisfying assignment a for C123Find values of all gates in C under aGive value of gate v to variable xv ; call this assignment a 0a 0 satisfies ϕC (exercise) Consider a satisfying assignment a for ϕC123Let a 0 be the restriction of a to only the input variablesValue of gate v under a 0 is the same as value of xv in aThus, a 0 satisfies CChandra & Manoj (UIUC)CS37441Fall 201541 / 57

Part IIIProof of Cook-Levin TheoremChandra & Manoj (UIUC)CS37442Fall 201542 / 57

Cook-Levin TheoremTheorem (Cook-Levin)SAT is NP-Complete.We have already seen that SAT is in NP.Need to prove that every language L NP, L P SATChandra & Manoj (UIUC)CS37443Fall 201543 / 57

Cook-Levin TheoremTheorem (Cook-Levin)SAT is NP-Complete.We have already seen that SAT is in NP.Need to prove that every language L NP, L P SATDifficulty: Infinite number of languages in NP. Must simultaneouslyshow a generic reduction strategy.Chandra & Manoj (UIUC)CS37443Fall 201543 / 57

High-level PlanWhat does it mean that L NP?L NP implies that there is a non-deterministic TM M andpolynomial p() such thatL {x Σ M accepts x in at most p( x ) steps}Chandra & Manoj (UIUC)CS37444Fall 201544 / 57

High-level PlanWhat does it mean that L NP?L NP implies that there is a non-deterministic TM M andpolynomial p() such thatL {x Σ M accepts x in at most p( x ) steps}We will describe a reduction fM that depends on M, p such that:fM takes as input a string x and outputs a SAT formula fM (x)fM runs in time polynomial in x x L if and only if fM (x) is satisfiableChandra & Manoj (UIUC)CS37444Fall 201544 / 57

Plan continuedxfMfM (x)poly-time computablefM (x) is satisfiable if and only if x LfM (x) is satisfiable if and only if non-det M accepts x in p( x ) stepsChandra & Manoj (UIUC)CS37445Fall 201545 / 57

Plan continuedxfMfM (x)poly-time computablefM (x) is satisfiable if and only if x LfM (x) is satisfiable if and only if non-det M accepts x in p( x ) stepsBIG IDEAfM (x) will express “M on input x accepts in p( x ) steps”fM (x) will encode a computation history of M on xfM (x) will be a carefully constructed CNF formulat s.t if we have asatisfying assignment to it, then we will be able to see a completeaccepting computation of M on x down to the last detail of wherethe head is, what transistion is chosen, what the tape contents are,at each step.Chandra & Manoj (UIUC)CS37445Fall 201545 / 57

Tableu of ComputationM runs in time p( x ) on x. Entire computation of M on x can berepresented by a “tableau”tape cell position1 2 3 40 1 0 0 11 0 0 0 123p( x )blanksstate q0blanksstate q2timep( x )Row i gives contents of all cells at time iAt time 0 tape has input x followed by blanksEach row long enough to hold all cells M might ever have scanned.Chandra & Manoj (UIUC)CS37446Fall 201546 / 57

Variable of fM (x)Four types of variable to describe computation of M on xT (b, h, i ) : tape cell at position h holds symbol b at time i .1 h p( x ), b Γ, 0 i p( x )H(h, i ): read/write head is at position h at time i .1 h p( x ), 0 i p( x )S(q, i ) state of M is q at time i q Q, 0 i p( x )I (j , i ) instruction number j is executed at time iM is non-deterministic, need to specify transitions in some way.Number transitions as 1, 2, . . . , where j ’th transition is qj , bj , qj0 , bj0 , dj indication (qj0 , bj0 , dj ) δ(qj , bj ),direction dj { 1, 0, 1}.Number of variables is O(p( x )2 ) where constant in O() hidesdependence on fixed machine M.Chandra & Manoj (UIUC)CS37447Fall 201547 / 57

NotationSomeVm abbreviations for ease of notationk 1 xk means x1 x2 . . . xmWmk 1xk means x1 x2 . . . xmL(x1 , x2 , . . . , xk ) is a formula that means exactly one ofx1 , x2 , . . . , xm is true. Can be converted to CNF formChandra & Manoj (UIUC)CS37448Fall 201548 / 57

Clauses of fM (x)fM (x) is the conjunction of 8 clause groups:fM (x) ϕ1 ϕ2 ϕ3 ϕ4 ϕ5 ϕ6 ϕ7 ϕ8where each ϕi is a CNF formula. Described in subsequent slides.Property: fM (x) is satisfied iff there is a truth assignment to thevariables that simultaneously satisfy ϕ1 , . . . , ϕ8 .Chandra & Manoj (UIUC)CS37449Fall 201549 / 57

ϕ1ϕ1 asserts (is true iff) the variables are set T/F indicating that Mstarts in state q0 at time 0 with tape contents containing x followedby blanks.Let x a1 a2 . . . anϕV1 S(q, 0) state at time 0 is q0VnandT (ah , h, 0) at time 0 cells 1 to n have a1 to anVh 1p( x Vh n 1 )T (B, h, 0) at time 0 cells n 1 to p( x ) have blanksandH(1, 0)head at time 0 is in position 1Chandra & Manoj (UIUC)CS37450Fall 201550 / 57

ϕ2ϕ2 asserts M in exactly one state at any time iϕ2 Vp( x )i 0 (S(q0 , i ), S(q1 , i ), . . . , S(q Q , i ))Chandra & Manoj (UIUC)CS37451Fall 201551 / 57

ϕ3ϕ3 asserts that each tape cell holds a unique symbol at any giventime.p( x ) p( x )ϕ3 i 0 (T (b1 , h, i ), T (b2 , h, i ), . . . , T (b Γ , h, i ))h 1For each time i and for each cell position h exactly one symbolb Γ at cell position h at time iChandra & Manoj (UIUC)CS37452Fall 201552 / 57

ϕ4ϕ4 asserts that the read/write head of M is in exactly one positionat any time ip( x )ϕ4 ( (H(1, i ), H(2, i ), . . . , H(p( x ), i )))i 0Chandra & Manoj (UIUC)CS37453Fall 201553 / 57

ϕ5ϕ5 asserts that M acceptsLet qa be unique accept state of Mwithout loss of generality assume M runs all p( x ) stepsϕ5 S(qa , p( x ))State at time p( x ) is qa the accept state.If we don’t want to make assumption of running for all stepsp( x )ϕ5 S(qa , i )i 1which means M enters accepts state at some time.Chandra & Manoj (UIUC)CS37454Fall 201554 / 57

ϕ6ϕ6 asserts that M executes a unique instruction at each timep( x )ϕ6 (I (1, i ), I (2, i ), . . . , I (m, i ))i 0where m is max instruction number.Chandra & Manoj (UIUC)CS37455Fall 201555 / 57

ϕ7ϕ7 ensures that variables don’t allow tape to change from onemoment to next if the read/write head was not there.“If head is not at position h at time i then at time i 1 the symbolat cell h must be unchanged” H(h, i ) T (b, h, i ) T (c, h, i 1)ϕ7 ih b6 csince A B is same as A B, rewrite above in CNF formϕ7 i(H(h, i ) T (b, h, i ) T (c, h, i 1))h b6 cChandra & Manoj (UIUC)CS37456Fall 201556 / 57

ϕ8ϕ8 asserts that changes in tableu/tape correspond to transitions ofM (as Lenny says, this is the big cookie).Let j ’th instruction be qj , bj , qj0 , bj0 , dj V VϕV8 i j (I (j , i ) S(qj , i )) If instr j executed at time i then state must be correct to do jV V0Vi j (I (j , i ) S(qj , i 1)) and at next time unit, state must be the proper next state for instr jV V VVH(h,Vi )) T (bj , h, i )] if j was executed and head was atihj [(I (j , i )position h, then cell h has correct symbol for jV V V0i 1)] if j was done then at time i withijh [(I (j , i ) H(h, i )) T (bj , h,Vhead at h then at next time step symbol bj0 was indeed written in position hV V Vijh [(I (j , i ) H(h, i )) H(h dj , i 1)] and head is moved properlyaccording to instr j .Chandra & Manoj (UIUC)CS37457Fall 201557 / 57

Proof of Correctness(Sketch)Given M, x, poly-time algorithm to construct fM (x)if fM (x) is satisfiable then the truth assignment completelyspecifies an accepting computation of M on xif M accepts x then the accepting computation leads to an”obvious” truth assignment to fM (x). Simply assign thevariables according to the state of M and cells at each time i .Thus M accepts x if and only if fM (x) is satisfiableChandra & Manoj (UIUC)CS37458Fall 201558 / 57

3-Color, Circuit-SAT and SAT Lecture 24 December 1, 2015 Chandra & Manoj (UIUC) CS374 1 Fall 2015 1 / 57. Recap . Graph 2-Coloring can be decided in polynomial time. G is 2-colorable i G is bipartite! There is a linear time algorithm to check if G is bipartite using BFS Chandra & Manoj (UIUC) CS374 9 Fall 2015 9 / 57 .