Transcription
CS 374: Algorithms & Models of Computation,Spring 2017Hamiltonian Cycle, 3-Color,Circuit-SATLecture 24April 25, 2017Chandra Chekuri (UIUC)CS3741Spring 20171 / 58
RecapNP: languages that have non-deterministic polynomial timealgorithmsChandra Chekuri (UIUC)CS3742Spring 20172 / 58
RecapNP: languages that have non-deterministic polynomial timealgorithmsA language L is NP-Complete iffL is in NPfor every L0 in NP, L0 P LChandra Chekuri (UIUC)CS3742Spring 20172 / 58
RecapNP: languages that have non-deterministic polynomial timealgorithmsA language L is NP-Complete iffL is in NPfor every L0 in NP, L0 P LL is NP-Hard if for every L0 in NP, L0 P L.Chandra Chekuri (UIUC)CS3742Spring 20172 / 58
RecapNP: languages that have non-deterministic polynomial timealgorithmsA language L is NP-Complete iffL is in NPfor every L0 in NP, L0 P LL is NP-Hard if for every L0 in NP, L0 P L.Theorem (Cook-Levin)SAT is NP-Complete.Chandra Chekuri (UIUC)CS3742Spring 20172 / 58
Pictorial ViewNP-HardNP-CNPPChandra Chekuri (UIUC)CS3743Spring 20173 / 58
P and NPPossible scenarios:1P NP.2P 6 NPChandra Chekuri (UIUC)CS3744Spring 20174 / 58
P and NPPossible scenarios:1P NP.2P 6 NPQuestion: Suppose P 6 NP. Is every problem in NP \ P alsoNP-Complete?Chandra Chekuri (UIUC)CS3744Spring 20174 / 58
P and NPPossible scenarios:1P NP.2P 6 NPQuestion: Suppose P 6 NP. Is every problem in NP \ P alsoNP-Complete?Theorem (Ladner)If P 6 NP then there is a problem/language X NP \ P such thatX is not NP-Complete.Chandra Chekuri (UIUC)CS3744Spring 20174 / 58
TodayNP-Completeness of three problems:Hamiltonian Cycle3-ColorCircuit SATImportant: understanding the problems and that they are hard.Proofs and reductions will be sketchy and mainly to give a flavorChandra Chekuri (UIUC)CS3745Spring 20175 / 58
Part INP-Completeness of HamiltonianCycleChandra Chekuri (UIUC)CS3746Spring 20176 / 58
Directed Hamiltonian CycleInput Given a directed graph G (V , E ) with n verticesGoal Does G have a Hamiltonian cycle?Chandra Chekuri (UIUC)CS3747Spring 20177 / 58
Directed Hamiltonian CycleInput Given a directed graph G (V , E ) with n verticesGoal Does G have a Hamiltonian cycle?A Hamiltonian cycle is a cycle in the graph thatvisits every vertex in G exactly onceChandra Chekuri (UIUC)CS3747Spring 20177 / 58
Is the following graph Hamiltonianan?(A) Yes.(B) No.Chandra Chekuri (UIUC)CS3748Spring 20178 / 58
Directed Hamiltonian Cycle is NP-CompleteDirected Hamiltonian Cycle is in NP: exerciseHardness: We will show3-SAT P Directed Hamiltonian CycleChandra Chekuri (UIUC)CS3749Spring 20179 / 58
ReductionGiven 3-SAT formula ϕ create a graph Gϕ such thatGϕ has a Hamiltonian cycle if and only if ϕ is satisfiableGϕ should be constructible from ϕ by a polynomial timealgorithm ANotation: ϕ has n variables x1 , x2 , . . . , xn and m clausesC1 , C2 , . . . , Cm .Chandra Chekuri (UIUC)CS37410Spring 201710 / 58
Reduction: First IdeasViewing SAT: Assign values to n variables, and each clauses has3 ways in which it can be satisfied.Construct graph with 2n Hamiltonian cycles, where each cyclecorresponds to some boolean assignment.Then add more graph structure to encode constraints onassignments imposed by the clauses.Chandra Chekuri (UIUC)CS37411Spring 201711 / 58
The Reduction: Phase ITraverse path i from left to right iff xi is set to trueEach path has 3(m 1) nodes where m is number of clauses inϕ; nodes numbered from left to right (1 to 3m 3)x1x2x3x4Chandra Chekuri (UIUC)CS37412Spring 201712 / 58
The Reduction: Phase IIAdd vertex cj for clause Cj . cj has edge from vertex 3j and tovertex 3j 1 on path i if xi appears in clause Cj , and has edgefrom vertex 3j 1 and to vertex 3j if xi appears in Cj .x1 x2 x4 x1 x2 x3x1x2x3x4Chandra Chekuri (UIUC)CS37413Spring 201713 / 58
The Reduction: Phase IIAdd vertex cj for clause Cj . cj has edge from vertex 3j and tovertex 3j 1 on path i if xi appears in clause Cj , and has edgefrom vertex 3j 1 and to vertex 3j if xi appears in Cj .x1 x2 x4 x1 x2 x3x1x2x3x4Chandra Chekuri (UIUC)CS37413Spring 201713 / 58
The Reduction: Phase IIAdd vertex cj for clause Cj . cj has edge from vertex 3j and tovertex 3j 1 on path i if xi appears in clause Cj , and has edgefrom vertex 3j 1 and to vertex 3j if xi appears in Cj .x1 x2 x4 ”Buffer” vertices x1 x2 x3x1x2x3x4Chandra Chekuri (UIUC)CS37413Spring 201713 / 58
The Reduction: Phase IIAdd vertex cj for clause Cj . cj has edge from vertex 3j and tovertex 3j 1 on path i if xi appears in clause Cj , and has edgefrom vertex 3j 1 and to vertex 3j if xi appears in Cj .x1 x2 x4 x1 x2 x3x1x2x3x4Chandra Chekuri (UIUC)CS37413Spring 201713 / 58
The Reduction: Phase IIAdd vertex cj for clause Cj . cj has edge from vertex 3j and tovertex 3j 1 on path i if xi appears in clause Cj , and has edgefrom vertex 3j 1 and to vertex 3j if xi appears in Cj .x1 x2 x4 x1 x2 x3x1x2x3x4Chandra Chekuri (UIUC)CS37413Spring 201713 / 58
The Reduction: Phase IIAdd vertex cj for clause Cj . cj has edge from vertex 3j and tovertex 3j 1 on path i if xi appears in clause Cj , and has edgefrom vertex 3j 1 and to vertex 3j if xi appears in Cj .x1 x2 x4 x1 x2 x3x1x2x3x4Chandra Chekuri (UIUC)CS37413Spring 201713 / 58
The Reduction: Phase IIAdd vertex cj for clause Cj . cj has edge from vertex 3j and tovertex 3j 1 on path i if xi appears in clause Cj , and has edgefrom vertex 3j 1 and to vertex 3j if xi appears in Cj .x1 x2 x4 x1 x2 x3x1x2x3x4Chandra Chekuri (UIUC)CS37413Spring 201713 / 58
Correctness ProofPropositionϕ has a satisfying assignment iff Gϕ has a Hamiltonian cycle.Proof. Let a be the satisfying assignment for ϕ. Define Hamiltoniancycle as followsIf a(xi ) 1 then traverse path i from left to rightIf a(xi ) 0 then traverse path i from right to leftFor each clause, path of at least one variable is in the “right”direction to splice in the node corresponding to clauseChandra Chekuri (UIUC)CS37414Spring 201714 / 58
Hamiltonian Cycle Satisfying assignmentSuppose Π is a Hamiltonian cycle in GϕIf Π enters cj (vertex for clause Cj ) from vertex 3j on path ithen it must leave the clause vertex on edge to 3j 1 on thesame path iIf not, then only unvisited neighbor of 3j 1 on path i is 3j 2Thus, we don’t have two unvisited neighbors (one to enterfrom, and the other to leave) to have a Hamiltonian CycleSimilarly, if Π enters cj from vertex 3j 1 on path i then itmust leave the clause vertex cj on edge to 3j on path iChandra Chekuri (UIUC)CS37415Spring 201715 / 58
Examplex1x2x3x4Chandra Chekuri (UIUC)CS37416Spring 201716 / 58
Hamiltonian Cycle Satisfying assignment(contd)Thus, vertices visited immediately before and after Ci areconnected by an edgeWe can remove cj from cycle, and get Hamiltonian cycle inG cjConsider Hamiltonian cycle in G {c1 , . . . cm }; it traverseseach path in only one direction, which determines the truthassignmentChandra Chekuri (UIUC)CS37417Spring 201717 / 58
Hamiltonian CycleProblemInput Given undirected graph G (V , E )Goal Does G have a Hamiltonian cycle? That is, is there acycle that visits every vertex exactly one (except startand end vertex)?Chandra Chekuri (UIUC)CS37418Spring 201718 / 58
NP-CompletenessTheoremHamiltonian cycle problem for undirected graphs isNP-Complete.Proof.The problem is in NP; proof left as exercise.Hardness proved by reducing Directed Hamiltonian Cycle to thisproblemChandra Chekuri (UIUC)CS37419Spring 201719 / 58
Reduction SketchGoal: Given directed graph G , need to construct undirected graphG 0 such that G has Hamiltonian Path iff G 0 has Hamiltonian pathReductionacvbChandra Chekuri (UIUC)dCS37420Spring 201720 / 58
Reduction SketchGoal: Given directed graph G , need to construct undirected graphG 0 such that G has Hamiltonian Path iff G 0 has Hamiltonian pathReductionReplace each vertex v by 3 vertices: vin , v , and voutacvbChandra Chekuri (UIUC)dCS37420Spring 201720 / 58
Reduction SketchGoal: Given directed graph G , need to construct undirected graphG 0 such that G has Hamiltonian Path iff G 0 has Hamiltonian pathReductionReplace each vertex v by 3 vertices: vin , v , and voutA directed edge (a, b) is replaced by edge (aout , bin )acvbChandra Chekuri (UIUC)dCS37420Spring 201720 / 58
Reduction SketchGoal: Given directed graph G , need to construct undirected graphG 0 such that G has Hamiltonian Path iff G 0 has Hamiltonian pathReductionReplace each vertex v by 3 vertices: vin , v , and voutA directed edge (a, b) is replaced by edge (aout , bin )aciaocvivbChandra Chekuri (UIUC)CS374vdibodvo20Spring 201720 / 58
Reduction: WrapupThe reduction is polynomial time (exercise)The reduction is correct (exercise)Chandra Chekuri (UIUC)CS37421Spring 201721 / 58
Hamiltonian PathInput Given a graph G (V , E ) with n verticesGoal Does G have a Hamiltonian path?A Hamiltonian path is a path in the graph thatvisits every vertex in G exactly onceChandra Chekuri (UIUC)CS37422Spring 201722 / 58
Hamiltonian PathInput Given a graph G (V , E ) with n verticesGoal Does G have a Hamiltonian path?A Hamiltonian path is a path in the graph thatvisits every vertex in G exactly onceTheoremDirected Hamiltonian Path and Undirected Hamiltonian Pathare NP-Complete.Chandra Chekuri (UIUC)CS37422Spring 201722 / 58
Part IINP-Completeness of GraphColoringChandra Chekuri (UIUC)CS37423Spring 201723 / 58
Graph ColoringProblem: Graph ColoringInstance: G (V , E ): Undirected graph, integer k.Question: Can the vertices of the graph be coloredusing k colors so that vertices connected by an edge donot get the same color?Chandra Chekuri (UIUC)CS37424Spring 201724 / 58
Graph 3-ColoringProblem: 3 ColoringInstance: G (V , E ): Undirected graph.Question: Can the vertices of the graph be coloredusing 3 colors so that vertices connected by an edge donot get the same color?Chandra Chekuri (UIUC)CS37425Spring 201725 / 58
Graph 3-ColoringProblem: 3 ColoringInstance: G (V , E ): Undirected graph.Question: Can the vertices of the graph be coloredusing 3 colors so that vertices connected by an edge donot get the same color?Chandra Chekuri (UIUC)CS37425Spring 201725 / 58
Graph ColoringObservation: If G is colored with k colors then each color class(nodes of same color) form an independent set in G . Thus, G can bepartitioned into k independent sets iff G is k-colorable.Chandra Chekuri (UIUC)CS37426Spring 201726 / 58
Graph ColoringObservation: If G is colored with k colors then each color class(nodes of same color) form an independent set in G . Thus, G can bepartitioned into k independent sets iff G is k-colorable.Graph 2-Coloring can be decided in polynomial time.Chandra Chekuri (UIUC)CS37426Spring 201726 / 58
Graph ColoringObservation: If G is colored with k colors then each color class(nodes of same color) form an independent set in G . Thus, G can bepartitioned into k independent sets iff G is k-colorable.Graph 2-Coloring can be decided in polynomial time.G is 2-colorable iff G is bipartite!Chandra Chekuri (UIUC)CS37426Spring 201726 / 58
Graph ColoringObservation: If G is colored with k colors then each color class(nodes of same color) form an independent set in G . Thus, G can bepartitioned into k independent sets iff G is k-colorable.Graph 2-Coloring can be decided in polynomial time.G is 2-colorable iff G is bipartite! There is a linear time algorithm tocheck if G is bipartite using BFSChandra Chekuri (UIUC)CS37426Spring 201726 / 58
Graph Coloring and Register AllocationRegister AllocationAssign variables to (at most) k registers such that variables neededat the same time are not assigned to the same registerInterference GraphVertices are variables, and there is an edge between two vertices, ifthe two variables are “live” at the same time.Observations[Chaitin] Register allocation problem is equivalent to coloring theinterference graph with k colorsMoreover, 3-COLOR P k-Register Allocation, for anyk 3Chandra Chekuri (UIUC)CS37427Spring 201727 / 58
Class Room SchedulingGiven n classes and their meeting times, are k rooms sufficient?Chandra Chekuri (UIUC)CS37428Spring 201728 / 58
Class Room SchedulingGiven n classes and their meeting times, are k rooms sufficient?Reduce to Graph k-Coloring problemCreate graph Ga node vi for each class ian edge between vi and vj if classes i and j conflictChandra Chekuri (UIUC)CS37428Spring 201728 / 58
Class Room SchedulingGiven n classes and their meeting times, are k rooms sufficient?Reduce to Graph k-Coloring problemCreate graph Ga node vi for each class ian edge between vi and vj if classes i and j conflictExercise: G is k-colorable iff k rooms are sufficientChandra Chekuri (UIUC)CS37428Spring 201728 / 58
Frequency Assignments in Cellular NetworksCellular telephone systems that use Frequency Division MultipleAccess (FDMA) (example: GSM in Europe and Asia and AT&T inUSA)Breakup a frequency range [a, b] into disjoint bands offrequencies [a0 , b0 ], [a1 , b1 ], . . . , [ak , bk ]Each cell phone tower (simplifying) gets one bandConstraint: nearby towers cannot be assigned same band,otherwise signals will interferenceChandra Chekuri (UIUC)CS37429Spring 201729 / 58
Frequency Assignments in Cellular NetworksCellular telephone systems that use Frequency Division MultipleAccess (FDMA) (example: GSM in Europe and Asia and AT&T inUSA)Breakup a frequency range [a, b] into disjoint bands offrequencies [a0 , b0 ], [a1 , b1 ], . . . , [ak , bk ]Each cell phone tower (simplifying) gets one bandConstraint: nearby towers cannot be assigned same band,otherwise signals will interferenceProblem: given k bands and some region with n towers, is there away to assign the bands to avoid interference?Can reduce to k-coloring by creating intereference/conflict graph ontowers.Chandra Chekuri (UIUC)CS37429Spring 201729 / 58
3 color this gadget.You are given three colors: red, green and blue. Can the followinggraph be three colored in a valid way (assuming that some of thenodes are already colored as indicated).(A) Yes.(B) No.Chandra Chekuri (UIUC)CS37430Spring 201730 / 58
3 color this gadget IIYou are given three colors: red, green and blue. Can the followinggraph be three colored in a valid way (assuming that some of thenodes are already colored as indicated).(A) Yes.(B) No.Chandra Chekuri (UIUC)CS37431Spring 201731 / 58
3-Coloring is NP-Complete3-Coloring is in NP.Non-deterministically guess a 3-coloring for each nodeCheck if for each edge (u, v ), the color of u is different fromthat of v .Hardness: We will show 3-SAT P 3-Coloring.Chandra Chekuri (UIUC)CS37432Spring 201732 / 58
Reduction IdeaStart with 3SAT formula (i.e., 3CNF formula) ϕ with n variablesx1 , . . . , xn and m clauses C1 , . . . , Cm . Create graph Gϕ such thatGϕ is 3-colorable iff ϕ is satisfiableneed to establish truth assignment for x1 , . . . , xn via colors forsome nodes in Gϕ .Chandra Chekuri (UIUC)CS37433Spring 201733 / 58
Reduction IdeaStart with 3SAT formula (i.e., 3CNF formula) ϕ with n variablesx1 , . . . , xn and m clauses C1 , . . . , Cm . Create graph Gϕ such thatGϕ is 3-colorable iff ϕ is satisfiableneed to establish truth assignment for x1 , . . . , xn via colors forsome nodes in Gϕ .create triangle with node True, False, BaseChandra Chekuri (UIUC)CS37433Spring 201733 / 58
Reduction IdeaStart with 3SAT formula (i.e., 3CNF formula) ϕ with n variablesx1 , . . . , xn and m clauses C1 , . . . , Cm . Create graph Gϕ such thatGϕ is 3-colorable iff ϕ is satisfiableneed to establish truth assignment for x1 , . . . , xn via colors forsome nodes in Gϕ .create triangle with node True, False, Basefor each variable xi two nodes vi and v̄i connected in a trianglewith common BaseChandra Chekuri (UIUC)CS37433Spring 201733 / 58
Reduction IdeaStart with 3SAT formula (i.e., 3CNF formula) ϕ with n variablesx1 , . . . , xn and m clauses C1 , . . . , Cm . Create graph Gϕ such thatGϕ is 3-colorable iff ϕ is satisfiableneed to establish truth assignment for x1 , . . . , xn via colors forsome nodes in Gϕ .create triangle with node True, False, Basefor each variable xi two nodes vi and v̄i connected in a trianglewith common BaseIf graph is 3-colored, either vi or v̄i gets the same color as True.Interpret this as a truth assignment to viChandra Chekuri (UIUC)CS37433Spring 201733 / 58
Reduction IdeaStart with 3SAT formula (i.e., 3CNF formula) ϕ with n variablesx1 , . . . , xn and m clauses C1 , . . . , Cm . Create graph Gϕ such thatGϕ is 3-colorable iff ϕ is satisfiableneed to establish truth assignment for x1 , . . . , xn via colors forsome nodes in Gϕ .create triangle with node True, False, Basefor each variable xi two nodes vi and v̄i connected in a trianglewith common BaseIf graph is 3-colored, either vi or v̄i gets the same color as True.Interpret this as a truth assignment to viNeed to add constraints to ensure clauses are satisfied (nextphase)Chandra Chekuri (UIUC)CS37433Spring 201733 / 58
FigureTFvnBasev1vnv1v2v2Chandra Chekuri (UIUC)CS37434Spring 201734 / 58
Clause Satisfiability GadgetFor each clause Cj (a b c), create a small gadget graphgadget graph connects to nodes corresponding to a, b, cneeds to implement OROR-gadget-graph:aa ba b cbcChandra Chekuri (UIUC)CS37435Spring 201735 / 58
OR-Gadget GraphProperty: if a, b, c are colored False in a 3-coloring then output nodeof OR-gadget has to be colored False.Property: if one of a, b, c is colored True then OR-gadget can be3-colored such that output node of OR-gadget is colored True.Chandra Chekuri (UIUC)CS37436Spring 201736 / 58
Reductioncreate triangle with nodes True, False, Basefor each variable xi two nodes vi and v̄i connected in a trianglewith common Basefor each clause Cj (a b c), add OR-gadget graph withinput nodes a, b, c and connect output node of gadget to bothFalse and Baseaa bTa b cbBasecChandra Chekuri (UIUC)FCS37437Spring 201737 / 58
Reductionaa bTa b cbBasecFClaimNo legal 3-coloring of above graph (with coloring of nodes T , F , Bfixed) in which a, b, c are colored False. If any of a, b, c are coloredTrue then there is a legal 3-coloring of above graph.Chandra Chekuri (UIUC)CS37438Spring 201738 / 58
3 coloring of the clause gadgetauwbarvwTscubvFFF - BADabawTscbbvbvwTscuTTFChandra Chekuri wscarTFTrTscTTTCS37439Spring 201739 / 58
Reduction OutlineExampleϕ (u v w ) (v x y )Variable and negationhave complementarycoloursLiterals get colour T or FPaletteTFNOR gatesChandra Chekuri (UIUC) uu vv ww xx yyCS37440Spring 201740 / 58
Correctness of Reductionϕ is satisfiable implies Gϕ is 3-colorableif xi is assigned True, color vi True and v̄i FalseChandra Chekuri (UIUC)CS37441Spring 201741 / 58
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.Chandra Chekuri (UIUC)CS37441Spring 201741 / 58
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.Chandra Chekuri (UIUC)CS37441Spring 201741 / 58
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 truthassignmentChandra Chekuri (UIUC)CS37441Spring 201741 / 58
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 Chekuri (UIUC)CS37441Spring 201741 / 58
Graph generated in reduction. from 3SAT to 3COLORTFXaaChandra Chekuri (UIUC)bcbCS374cd42dSpring 201742 / 58
Part IIICircuit SATChandra Chekuri (UIUC)CS37443Spring 201743 / 58
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 Chekuri (UIUC)CS37444Spring 201744 / 58
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 Chekuri (UIUC)CS37444Spring 201744 / 58
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 Chekuri (UIUC)CS37444Spring 201744 / 58
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 Chekuri (UIUC)CS37445Spring 201745 / 58
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 Chekuri (UIUC)CS37445Spring 201745 / 58
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 Chekuri (UIUC)CS37446Spring 201746 / 58
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 Chekuri (UIUC)CS37446Spring 201746 / 58
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 Chekuri (UIUC)CS37447Spring 201747 / 58
Example ϕ x1 x3 x4 x1 x2 x3 x2 x3 x4Chandra Chekuri (UIUC)CS37448Spring 201748 / 58
Converting a circuit into a CNF formulaLabel the nodesOutput:Output: , k 1 ? ?0 , f?1,aInputs , h , g?,b?,c0,d?,eInputs(A) Input circuitChandra Chekuri (UIUC) , j , i(B) Label the nodes.CS37449Spring 201749 / 58
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 Chekuri (UIUC)xk(C) Introduce var for each node.CS37450Spring 201750 / 58
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 Chekuri (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.51Spring 201751 / 58
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 Chekuri (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 ) xdxaCS37452Spring 201752 / 58
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 Chekuri (UIUC)CS37453Spring 201753 / 58
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 Chekuri (UIUC) CS374(xu xv )both true.( xu xv )54Spring 201754 / 58
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 Chekuri (UIUC) is trueCS374(xv xu ),(xv xw ),all true.( xv xu xw ) 55Spring 201755 / 58
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 Chekuri (UIUC) CS374( xv xu ),( xv xw ),all true.(xv xu xw )56Spring 201756 / 58
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 Chekuri (UIUC)CS37457Spring 201757 / 58
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 Chekuri (UIUC)CS37458Spring 201758 / 58
List of NP-Complete Problems to nt SetCliqueVertex CoverHamilton Cycle and Hamilton Path in both directed andundirected graphs3Color and ColorChandra Chekuri (UIUC)CS37459Spring 201759 / 58
Spring 2017 Hamiltonian Cycle, 3-Color, Circuit-SAT Lecture 24 April 25, 2017 Chandra Chekuri (UIUC) CS374 1 Spring 2017 1 / 58. Recap NP: languages that have non-deterministic polynomial time algorithms A language
