Transcription
CS 473: Algorithms, Spring 2021SAT, NP, NP-CompletenessLecture 21April 22, 2021Most slides are courtesy Prof. ChekuriRuta (UIUC)CS4731Spring 20211 / 55
Part IThe Satisfiability Problem (SAT)Ruta (UIUC)CS4732Spring 20212 / 55
Propositional FormulasDefinitionConsider a set of boolean variables x1 , x2 , . . . xn .1A literal is either a boolean variable xi or its negation xi .Ruta (UIUC)CS4733Spring 20213 / 55
Propositional FormulasDefinitionConsider a set of boolean variables x1 , x2 , . . . xn .1A literal is either a boolean variable xi or its negation xi .2A clause is a disjunction of literals.For example, x1 x2 x4 is a clause.Ruta (UIUC)CS4733Spring 20213 / 55
Propositional FormulasDefinitionConsider a set of boolean variables x1 , x2 , . . . xn .1A literal is either a boolean variable xi or its negation xi .2A clause is a disjunction of literals.For example, x1 x2 x4 is a clause.3A formula in conjunctive normal form (CNF) ispropositional formula which is a conjunction of clauses1(x1 x2 x4 ) (x2 x3 ) x5 is a CNF formula.Ruta (UIUC)CS4733Spring 20213 / 55
Propositional FormulasDefinitionConsider a set of boolean variables x1 , x2 , . . . xn .1A literal is either a boolean variable xi or its negation xi .2A clause is a disjunction of literals.For example, x1 x2 x4 is a clause.3A formula in conjunctive normal form (CNF) ispropositional formula which is a conjunction of clauses14(x1 x2 x4 ) (x2 x3 ) x5 is a CNF formula.A formula ϕ is a 3CNF:A CNF formula such that every clause has exactly 3 literals.1(x1 x2 x4 ) (x2 x3 x1 ) is a 3CNF formula, but(x1 x2 x4 ) (x2 x3 ) x5 is not.Ruta (UIUC)CS4733Spring 20213 / 55
SatisfiabilityProblem: SATInstance: A CNF formula ϕ.Question: Is there a truth assignment to the variable ofϕ such that ϕ evaluates to true?Problem: 3SATInstance: A 3CNF formula ϕ.Question: Is there a truth assignment to the variable ofϕ such that ϕ evaluates to true?Ruta (UIUC)CS4734Spring 20214 / 55
SatisfiabilitySATGiven a CNF formula ϕ, is there a truth assignment to variablessuch that ϕ evaluates to true?Example12(x1 x2 x4 ) (x2 x3 ) x5 is satisfiable; takex1 , x2 , . . . x5 to be all true(x1 x2 ) ( x1 x2 ) ( x1 x2 ) (x1 x2 ) is notsatisfiable.Ruta (UIUC)CS4735Spring 20215 / 55
Importance of SAT and 3SAT1234SAT and 3SAT are basic constraint satisfaction problems.Many different problems can reduced to them because of thesimple yet powerful expressively of logical constraints.Arise naturally in many applications involving hardware andsoftware verification and correctness.As we will see, it is a fundamental problem in theory ofNP-Completeness.Ruta (UIUC)CS4736Spring 20216 / 55
3SAT P SAT123SAT P SAT.Because.A 3SAT instance is also an instance of SAT.Ruta (UIUC)CS4737Spring 20217 / 55
SAT P 3SATClaimSAT P 3SAT.Ruta (UIUC)CS4738Spring 20218 / 55
SAT P 3SATClaimSAT P 3SAT.Given ϕ a SAT formula we create a 3SAT formula ϕ0 such that1ϕ is satisfiable iff ϕ0 is satisfiable.2ϕ0 can be constructed from ϕ in time polynomial in ϕ .Ruta (UIUC)CS4738Spring 20218 / 55
SAT P 3SATHow SAT is different from 3SAT?In SAT clauses might have arbitrary length: 1, 2, 3, . . . variables: x y z w x y z w u xIn 3SAT every clause must have exactly 3 different literals.Ruta (UIUC)CS4739Spring 20219 / 55
SAT P 3SATHow SAT is different from 3SAT?In SAT clauses might have arbitrary length: 1, 2, 3, . . . variables: x y z w x y z w u xIn 3SAT every clause must have exactly 3 different literals.Consider x y z w Replace it with x y α α w uRuta (UIUC)CS4739 Spring 20219 / 55
SAT P 3SATHow SAT is different from 3SAT?In SAT clauses might have arbitrary length: 1, 2, 3, . . . variables: x y z w x y z w u xIn 3SAT every clause must have exactly 3 different literals.Consider x y z w Replace it with x y α α w u123 Pad short clauses so they have 3 literals.Break long clauses into shorter clauses. (Need to add newvariables)Repeat the above till we have a 3CNF.Ruta (UIUC)CS4739Spring 20219 / 55
What about 2SAT?Ruta (UIUC)CS47310Spring 202110 / 55
What about 2SAT?2SAT can be solved in polynomial time! (specifically, linear time!)Ruta (UIUC)CS47310Spring 202110 / 55
What about 2SAT?2SAT can be solved in polynomial time! (specifically, linear time!)No known polynomial time reduction from SAT (or 3SAT) to2SAT. If there was, then SAT and 3SAT would be solvable inpolynomial time.Ruta (UIUC)CS47310Spring 202110 / 55
What about 2SAT?2SAT can be solved in polynomial time! (specifically, linear time!)No known polynomial time reduction from SAT (or 3SAT) to2SAT. If there was, then SAT and 3SAT would be solvable inpolynomial time.Why the reduction from 3SAT to 2SAT fails?Consider a clause (x y z). We need to reduce it to a collectionof 2CNF clauses. Introduce a face variable α, and rewrite this asor(x y α) ( α z)(x α) ( α y z)(bad! clause with 3 vars)(bad! clause with 3 vars).(In animal farm language: 2SAT good, 3SAT bad.)Ruta (UIUC)CS47310Spring 202110 / 55
What about 2SAT?A challenging exercise: Given a 2SAT formula design an efficientalgorithm to compute its satisfying assignment.Look in books etc.Ruta (UIUC)CS47311Spring 202111 / 55
Independent SetProblem: Independent SetInstance: A graph G, integer k.Question: Is there an independent set in G of size k?Ruta (UIUC)CS47312Spring 202112 / 55
Independent SetProblem: Independent SetInstance: A graph G, integer k.Question: Is there an independent set in G of size k?3SAT P Independent SetLater (if time permits)Ruta (UIUC)CS47312Spring 202112 / 55
Part IIDefinition of P and NPRuta (UIUC)CS47313Spring 202113 / 55
Problems and Algorithms: Formal ApproachDecision Problems12Problem Instance: Binary string s, with size s Problem: A set X of strings on which the answer should be“yes”; we call these YES instances of X . Strings not in X areNO instances of X .Definition12A is an algorithm for problem X if A(s) ”yes” iff s X .A is said to have a polynomial running time if there is apolynomial p(·) such that for every string s, A(s) terminates inat most O(p( s )) steps.Ruta (UIUC)CS47314Spring 202114 / 55
Polynomial TimeDefinitionPolynomial time (denoted by P) is the class of all (decision)problems that have an algorithm that solves it in polynomial time.Ruta (UIUC)CS47315Spring 202115 / 55
Polynomial TimeDefinitionPolynomial time (denoted by P) is the class of all (decision)problems that have an algorithm that solves it in polynomial time.ExampleProblems in P include1Is there a shortest path from s to t of length k in G ?2Is there a flow of value k in network G ?3Is there an assignment to variables to satisfy given linearconstraints?Ruta (UIUC)CS47315Spring 202115 / 55
Deterministic Turing MachineP (polynomial-time): problems that deterministic TM solves inpolynomial time.Ruta (UIUC)CS47316Spring 202116 / 55
Nondeterministic Turing MachineNP (nondeterministic polynomial time): problems thatnondeterministc TM solves in polynomial time.Ruta (UIUC)CS47317Spring 202117 / 55
Problems with no known polynomial timealgorithmsProblems12345Independent SetVertex CoverSet CoverSAT3SATThere are of course undecidable problems (no algorithm at all!) butmany problems that we want to solve are of similar flavor to theabove.Question: What is common to above problems?Ruta (UIUC)CS47318Spring 202118 / 55
Efficient CheckabilityAbove problems share the following feature:CheckabilityFor any YES instance IX of X there is a proof/certificate/solutionthat is of length poly( IX ) such that given a proof one can efficientlycheck that IX is indeed a YES instance.Ruta (UIUC)CS47319Spring 202119 / 55
Efficient CheckabilityAbove problems share the following feature:CheckabilityFor any YES instance IX of X there is a proof/certificate/solutionthat is of length poly( IX ) such that given a proof one can efficientlycheck that IX is indeed a YES instance.Examples:1SAT formula ϕ: proof is a satisfying assignment.2Independent Set in graph G and k:Ruta (UIUC)CS47319Spring 202119 / 55
Efficient CheckabilityAbove problems share the following feature:CheckabilityFor any YES instance IX of X there is a proof/certificate/solutionthat is of length poly( IX ) such that given a proof one can efficientlycheck that IX is indeed a YES instance.Examples:1SAT formula ϕ: proof is a satisfying assignment.2Independent Set in graph G and k: a subset S of vertices.Ruta (UIUC)CS47319Spring 202119 / 55
CertifiersDefinition (Efficient Certifier.)An algorithm C is an efficient certifier for problem X , if there is apolynomial p(·) such that,? Ix X if and only if123there is a string t (certificate/proof) with t p( Ix ),C (Ix , t) ”yes”,and C runs in polynomial time in Ix .Ruta (UIUC)CS47320Spring 202120 / 55
CertifiersDefinition (Efficient Certifier.)An algorithm C is an efficient certifier for problem X , if there is apolynomial p(·) such that,? Ix X if and only if123there is a string t (certificate/proof) with t p( Ix ),C (Ix , t) ”yes”,and C runs in polynomial time in Ix .“Guess” the certificate and verify nondeterministic TM.Ruta (UIUC)CS47320Spring 202120 / 55
Examples1Independent set: Does G (V , E ) have an independent set ofsize k?12Certificate: Set S V .Certifier: Check S k and no pair of vertices in S isconnected by an edge.Ruta (UIUC)CS47321Spring 202121 / 55
Examples1Independent set: Does G (V , E ) have an independent set ofsize k?122Certificate: Set S V .Certifier: Check S k and no pair of vertices in S isconnected by an edge.Vertex cover: Does G have a vertex cover of size k?Ruta (UIUC)CS47321Spring 202121 / 55
Examples1Independent set: Does G (V , E ) have an independent set ofsize k?122Certificate: Set S V .Certifier: Check S k and no pair of vertices in S isconnected by an edge.Vertex cover: Does G have a vertex cover of size k?12Certificate: S V .Certifier: Check S k and that for every edge at least oneendpoint is in S.Ruta (UIUC)CS47321Spring 202121 / 55
Examples1Independent set: Does G (V , E ) have an independent set ofsize k?122Vertex cover: Does G have a vertex cover of size k?123Certificate: Set S V .Certifier: Check S k and no pair of vertices in S isconnected by an edge.Certificate: S V .Certifier: Check S k and that for every edge at least oneendpoint is in S.SAT: Does formula ϕ have a satisfying truth assignment?Ruta (UIUC)CS47321Spring 202121 / 55
Examples1Independent set: Does G (V , E ) have an independent set ofsize k?122Vertex cover: Does G have a vertex cover of size k?123Certificate: Set S V .Certifier: Check S k and no pair of vertices in S isconnected by an edge.Certificate: S V .Certifier: Check S k and that for every edge at least oneendpoint is in S.SAT: Does formula ϕ have a satisfying truth assignment?12Certificate: Assignment a of 0/1 values to each variable.Certifier: Check each clause under a and say “yes” if all clausesare true.Ruta (UIUC)CS47321Spring 202121 / 55
Nondeterministic Polynomial TimeAlternate definitionDefinitionNondeterministic Polynomial Time (denoted by NP) is the class ofall problems that have efficient certifiers.Ruta (UIUC)CS47322Spring 202122 / 55
Nondeterministic Polynomial TimeAlternate definitionDefinitionNondeterministic Polynomial Time (denoted by NP) is the class ofall problems that have efficient certifiers.ExampleIndependent Set, Vertex Cover, Set Cover, SAT, 3SAT, andComposite are all examples of problems in NP.“Guess” the certificate and verify nondeterministic TM.Ruta (UIUC)CS47322Spring 202122 / 55
Nondeterministic Polynomial TimeAlternate definitionDefinitionNondeterministic Polynomial Time (denoted by NP) is the class ofall problems that have efficient certifiers.ExampleIndependent Set, Vertex Cover, Set Cover, SAT, 3SAT, andComposite are all examples of problems in NP.“Guess” the certificate and verify nondeterministic TM.nondeterministic TM Path to an “accept” state is the certificate.Ruta (UIUC)CS47322Spring 202122 / 55
Asymmetry in Definition of NPNote that only YES instances have a short proof/certificate. NOinstances need not have a short certificate.ExampleSAT formula ϕ. No easy way to prove that ϕ is NOT satisfiable!More on this and co-NP later on.Ruta (UIUC)CS47323Spring 202123 / 55
P versus NPPropositionP NP.Ruta (UIUC)CS47324Spring 202124 / 55
P versus NPPropositionP NP.For a problem in P no need for a certificate!Proof.Consider problem X P with algorithm A.1Certifier C on input Ix , t, runs A(Ix ) and returns the answer.C runs in polynomial time.If Ix X , then for every t, C (Ix , t) ”yes”.If Ix 6 X , then for every t, C (Ix , t) ”no”.Ruta (UIUC)CS47324Spring 202124 / 55
Exponential TimeDefinitionExponential Time (denoted EXP) is the collection of all problemsthat have an algorithm which on input Ix runs in exponential time,i.e., O(2poly( Ix ) ).Ruta (UIUC)CS47325Spring 202125 / 55
Exponential TimeDefinitionExponential Time (denoted EXP) is the collection of all problemsthat have an algorithm which on input Ix runs in exponential time,i.e., O(2poly( Ix ) ).3Example: O(2n ), O(2n log n ), O(2n ), .Problems:1SAT: try all possible truth assignment to variables.2Independent Set: try all possible subsets of vertices.3Vertex Cover: try all possible subsets of vertices.Ruta (UIUC)CS47325Spring 202125 / 55
NP versus EXPPropositionNP EXP.Proof.Let X NP with certifier C . Need to design an exponential timealgorithm for X .1For every t, with t p( Ix ) run C (Ix , t); answer “yes” ifany one of these calls returns “yes”.2The above algorithm correctly solves X (exercise).3Algorithm runs in O(q( Ix p( Ix ))2p( Ix ) ), where q is therunning time of C .Ruta (UIUC)CS47326Spring 202126 / 55
Is NP efficiently solvable?We know P NP EXP.Ruta (UIUC)CS47327Spring 202127 / 55
Is NP efficiently solvable?We know P NP EXP.If P NP this implies that.(A) Vertex Cover can be solved in polynomial time.(B) P EXP.(C) EXP P.(D) All of the above.Ruta (UIUC)CS47327Spring 202127 / 55
Is NP efficiently solvable?We know P NP EXP.Big QuestionIs there a problem in NP that does not belong to P? Or is P NP?Ruta (UIUC)CS47328Spring 202128 / 55
Is NP efficiently solvable?We know P NP EXP.Big QuestionIs there a problem in NP that does not belong to P? Or is P NP?StatusRelationship between P and NP remains one of the most importantopen problems in mathematics/computer science.Consensus: Most people feel/believe P 6 NP.Resolving P versus NP is a Clay Millennium Prize Problem. You canwin a million dollars in addition to a Turing award and major fame!Ruta (UIUC)CS47328Spring 202128 / 55
If P NP . . .Or: If pigs could fly then life would be sweet.1234Many important optimization problems can be solved efficiently.The RSA cryptosystem can be broken.No security on the web.No e-commerce . . .Ruta (UIUC)CS47329Spring 202129 / 55
If P NP . . .Or: If pigs could fly then life would be sweet.12345Many important optimization problems can be solved efficiently.The RSA cryptosystem can be broken.No security on the web.No e-commerce . . .Creativity can be automated! Proofs for mathematical statementcan be found by computers automatically (if short ones exist).Ruta (UIUC)CS47329Spring 202129 / 55
Part IIINP-Completeness and Cook-LevinTheoremRuta (UIUC)CS47330Spring 202130 / 55
“Hardest” ProblemsQuestionWhat is the hardest problem in NP? How do we define it?Towards a definition12Hardest problem must be in NP.Hardest problem must be at least as “difficult” as every otherproblem in NP.Ruta (UIUC)CS47331Spring 202131 / 55
NP-Complete ProblemsDefinitionA problem X is said to be NP-Hard if1(Hardness) Y NP, we have that Y P X.Ruta (UIUC)CS47332Spring 202132 / 55
NP-Complete ProblemsDefinitionA problem X is said to be NP-Hard if1(Hardness) Y NP, we have that Y P X.DefinitionA problem X is said to be NP-Complete if1X NP, and2X is NP-HardRuta (UIUC)CS47332Spring 202132 / 55
NP-Complete ProblemsDefinitionA problem X is said to be NP-Hard if1(Hardness) Y NP, we have that Y P X.DefinitionA problem X is said to be NP-Complete if1X NP, and2X is NP-HardAn NP-Hard problem need not be in NP!Example: Halting problem is NP-Hard (why?) but notNP-Complete.Ruta (UIUC)CS47332Spring 202132 / 55
Solving NP-Complete ProblemsPropositionSuppose X is NP-Complete. Then X can be solved in polynomialtime if and only if P NP.Proof. Suppose X can be solved in polynomial time12Let Y NP. We know Y P X.Then Y can be solved in polynomial time. Y P.Ruta (UIUC)CS47333Spring 202133 / 55
Solving NP-Complete ProblemsPropositionSuppose X is NP-Complete. Then X can be solved in polynomialtime if and only if P NP.Proof. Suppose X can be solved in polynomial time1234Let Y NP. We know Y P X.Then Y can be solved in polynomial time. Y P.Thus, Y NP Y P; NP P.Since P NP, we have P NP.Ruta (UIUC)CS47333Spring 202133 / 55
Solving NP-Complete ProblemsPropositionSuppose X is NP-Complete. Then X can be solved in polynomialtime if and only if P NP.Proof. Suppose X can be solved in polynomial time1234Let Y NP. We know Y P X.Then Y can be solved in polynomial time. Y P.Thus, Y NP Y P; NP P.Since P NP, we have P NP. Since P NP, and X NP, we have a polynomial timealgorithm for X .Ruta (UIUC)CS47333Spring 202133 / 55
Consequences of proving NP-CompletenessIf X is NP-Complete1Since we believe P 6 NP,2and solving X efficiently implies P NP.X is unlikely to be efficiently solvable.Ruta (UIUC)CS47334Spring 202134 / 55
Consequences of proving NP-CompletenessIf X is NP-Complete1Since we believe P 6 NP,2and solving X efficiently implies P NP.X is unlikely to be efficiently solvable.At the very least, many smart people before you have failed to findan efficient algorithm for X .Ruta (UIUC)CS47334Spring 202134 / 55
Consequences of proving NP-CompletenessIf X is NP-Complete1Since we believe P 6 NP,2and solving X efficiently implies P NP.X is unlikely to be efficiently solvable.At the very least, many smart people before you have failed to findan efficient algorithm for X .Ruta (UIUC)CS47334Spring 202134 / 55
Consequences of proving NP-CompletenessIf X is NP-Complete1Since we believe P 6 NP,2and solving X efficiently implies P NP.X is unlikely to be efficiently solvable.At the very least, many smart people before you have failed to findan efficient algorithm for X .(This is proof by mob opinion — take with a grain of salt.)Ruta (UIUC)CS47334Spring 202134 / 55
NP-Complete ProblemsQuestionAre there any problems that are NP-Complete?AnswerYes! Many, many problems are NP-Complete.Ruta (UIUC)CS47335Spring 202135 / 55
NP-Complete ProblemsQuestionAre there any problems that are NP-Complete?AnswerYes! Many, many problems are NP-Complete.Cook-Levin Theorem:TheoremSAT is NP-Complete.Ruta (UIUC)CS47335Spring 202135 / 55
NP-Complete ProblemsQuestionAre there any problems that are NP-Complete?AnswerYes! Many, many problems are NP-Complete.Cook-Levin Theorem:TheoremSAT is NP-Complete.Using reductions one can prove that many other problems areNP-CompleteRuta (UIUC)CS47335Spring 202135 / 55
Proving that a problem X is NP-CompleteTo prove X is NP-Complete, show1Show X is in NP.122certificate/proof of polynomial size in inputpolynomial time certifier C (s, t)Reduction from a known NP-Complete problem such as 3SATor SAT to XRuta (UIUC)CS47336Spring 202136 / 55
Proving that a problem X is NP-CompleteTo prove X is NP-Complete, show1Show X is in NP.122certificate/proof of polynomial size in inputpolynomial time certifier C (s, t)Reduction from a known NP-Complete problem such as 3SATor SAT to XSAT P X implies that every NP problem Y P X . Why?Ruta (UIUC)CS47336Spring 202136 / 55
Proving that a problem X is NP-CompleteTo prove X is NP-Complete, show1Show X is in NP.122certificate/proof of polynomial size in inputpolynomial time certifier C (s, t)Reduction from a known NP-Complete problem such as 3SATor SAT to XSAT P X implies that every NP problem Y P X . Why?Transitivity of reductions:Y P SAT and SAT P X and hence Y P X .Ruta (UIUC)CS47336Spring 202136 / 55
Recap . . .Problems123456Independent SetCliqueVertex CoverSet CoverSAT3SATRuta (UIUC)CS47337Spring 202137 / 55
Recap . . .Problems123456Independent SetCliqueVertex CoverSet CoverSAT3SATRelationship3SAT P Independent SetRuta (UIUC)CS47337Spring 202137 / 55
Recap . . .Problems123456Independent SetCliqueVertex CoverSet CoverSAT3SATRelationship P P3SAT P Independent Set P Clique P Vertex CoverRuta (UIUC)CS47337Spring 202137 / 55
Recap . . .Problems123456Independent SetCliqueVertex CoverSet CoverSAT3SATRelationship P P3SAT P Independent Set P Clique P Vertex Cover P Set CoverRuta (UIUC)CS47337Spring 202137 / 55
Recap . . .Problems123456Independent SetCliqueVertex CoverSet CoverSAT3SATRelationship P P3SAT P Independent Set P Clique P Vertex Cover P Set Cover3SAT P SAT P 3SATRuta (UIUC)CS47337Spring 202137 / 55
NP-Completeness via Reductions12345678SAT is NP-Complete.SAT P 3-SAT and hence 3-SAT is NP-Complete.3-SAT P Independent Set (which is in NP) and henceIndependent Set is NP-Complete.Clique is NP-CompleteVertex Cover is NP-CompleteSet Cover is NP-CompleteHamilton Cycle is NP-Complete3-Color is NP-CompleteRuta (UIUC)CS47338Spring 202138 / 55
NP-Completeness via Reductions12345678SAT is NP-Complete.SAT P 3-SAT and hence 3-SAT is NP-Complete.3-SAT P Independent Set (which is in NP) and henceIndependent Set is NP-Complete.Clique is NP-CompleteVertex Cover is NP-CompleteSet Cover is NP-CompleteHamilton Cycle is NP-Complete3-Color is NP-CompleteHundreds and thousands of different problems from many areas ofscience and engineering have been shown to be NP-Complete.A surprisingly frequent phenomenon!Ruta (UIUC)CS47338Spring 202138 / 55
3SAT P Independent SetThe reduction 3SAT P Independent SetInput: Given a 3CNF formula ϕGoal: Construct a graph Gϕ and number k such that Gϕ has anindependent set of size k if and only if ϕ is satisfiable.Ruta (UIUC)CS47339Spring 202139 / 55
3SAT P Independent SetThe reduction 3SAT P Independent SetInput: Given a 3CNF formula ϕGoal: Construct a graph Gϕ and number k such that Gϕ has anindependent set of size k if and only if ϕ is satisfiable.Gϕ should be constructable in time polynomial in size of ϕRuta (UIUC)CS47339Spring 202139 / 55
3SAT P Independent SetThe reduction 3SAT P Independent SetInput: Given a 3CNF formula ϕGoal: Construct a graph Gϕ and number k such that Gϕ has anindependent set of size k if and only if ϕ is satisfiable.Gϕ should be constructable in time polynomial in size of ϕImportance of reduction: Although 3SAT is much more expressive, itcan be reduced to a seemingly specialized Independent Set problem.Ruta (UIUC)CS47339Spring 202139 / 55
Interpreting 3SATThere are two ways to think about 3SATRuta (UIUC)CS47340Spring 202140 / 55
Interpreting 3SATThere are two ways to think about 3SAT1Find a way to assign 0/1 (false/true) to the variables such thatthe formula evaluates to true, that is each clause evaluates totrue.Ruta (UIUC)CS47340Spring 202140 / 55
Interpreting 3SATThere are two ways to think about 3SAT1Find a way to assign 0/1 (false/true) to the variables such thatthe formula evaluates to true, that is each clause evaluates totrue.2Pick a literal from each clause and find a truth assignment tomake all of them trueRuta (UIUC)CS47340Spring 202140 / 55
Interpreting 3SATThere are two ways to think about 3SAT1Find a way to assign 0/1 (false/true) to the variables such thatthe formula evaluates to true, that is each clause evaluates totrue.2Pick a literal from each clause and find a truth assignment tomake all of them true. You will fail if two of the literals you pickare in conflict, i.e., you pick xi and xiWe will take the second view of 3SAT to construct the reduction.Ruta (UIUC)CS47340Spring 202140 / 55
The Reduction1Gϕ will have one vertex for each literal in a clause x1x2 x1 x2x3x1x3x2x4Figure: Graph forϕ ( x1 x2 x3 ) (x1 x2 x3 ) ( x1 x2 x4 )Ruta (UIUC)CS47341Spring 202141 / 55
The Reduction12Gϕ will have one vertex for each literal in a clauseConnect the 3 literals in a clause to form a triangle; theindependent set will pick at most one vertex from each clause,which will correspond to the literal to be set to true x1x2 x1 x2x3x1x3x2x4Figure: Graph forϕ ( x1 x2 x3 ) (x1 x2 x3 ) ( x1 x2 x4 )Ruta (UIUC)CS47341Spring 202141 / 55
The Reduction12Gϕ will have one vertex for each literal in a clauseConnect the 3 literals in a clause to form a triangle; theindependent set will pick at most one vertex from each clause,which will correspond to the literal to be set to true x1x2 x1 x2x3x1x3x2x4Figure: Graph forϕ ( x1 x2 x3 ) (x1 x2 x3 ) ( x1 x2 x4 )Ruta (UIUC)CS47341Spring 202141 / 55
The Reduction123Gϕ will have one vertex for each literal in a clauseConnect the 3 literals in a clause to form a triangle; theindependent set will pick at most one vertex from each clause,which will correspond to the literal to be set to trueConnect 2 vertices if they label complementary literals; thisensures that the literals corresponding to the independent set donot have a conflict x1x2 x1 x2x3x1x3x2x4Figure: Graph forϕ ( x1 x2 x3 ) (x1 x2 x3 ) ( x1 x2 x4 )Ruta (UIUC)CS47341Spring 202141 / 55
The Reduction1234Gϕ will have one vertex for each literal in a clauseConnect the 3 literals in a clause to form a triangle; theindependent set will pick at most one vertex from each clause,which will correspond to the literal to be set to trueConnect 2 vertices if they label complementary literals; thisensures that the literals corresponding to the independent set donot have a conflictTake k to be the number of clauses x1x2 x1 x2x3x1x3x2x4Figure: Graph forϕ ( x1 x2 x3 ) (x1 x2 x3 ) ( x1 x2 x4 )Ruta (UIUC)CS47341Spring 202141 / 55
CorrectnessPropositionϕ is satisfiable iff Gϕ has an independent set of size k ( number ofclauses in ϕ).Proof. Let a be the truth assignment satisfying ϕRuta (UIUC)CS47342Spring 202142 / 55
CorrectnessPropositionϕ is satisfiable iff Gϕ has an independent set of size k ( number ofclauses in ϕ).Proof. Let a be the truth assignment satisfying ϕ1Pick one of the vertices, corresponding to true literals under a,from each triangle. This is an independent set of theappropriate sizeRuta (UIUC)CS47342Spring 202142 / 55
Correctness (contd)Propositionϕ is satisfiable iff Gϕ has an independent set of size k ( number ofclauses in ϕ).Proof. Let S be an independent set of size k123S must contain exactly one vertex from each clauseS cannot contain vertices labeled by conflicting clausesThus, it is possible to obtain a truth assignment that makes inthe literals in S true; such an assignment satisfies one literal inevery clauseRuta (UIUC)CS47343Spring 202143 / 55
Part IVco-NPRuta (UIUC)CS47344Spring 202144 / 55
NP vs co-NPNP: Problems with polynomial time verifier for a “yes” instance.SAT: Given a CNF formula φ, does there exists a satisfying assignment?- Poly-time verification (proof) for “yes” instances.Ruta (UIUC)CS47345Spring 202145 / 55
NP vs co-NPNP: Problems with polynomial time verifier for a “yes” instance.SAT: Given a CNF formula φ, does there exists a satisfying assignment?- Poly-time verification (proof) for “yes” instances.DefinitionGiven a decision problem X , its complement X̄ is the same problem with“yes” and “no” answeres reversed.Ruta (UIUC)CS47345Spring 202145 / 55
NP vs co-NPNP: Problems with polynomial time verifier for a “yes” instance.SAT: Given a CNF formula φ, does there exists a satisfying assignment?- Poly-time verification (proof) for “yes” instances.DefinitionGiven a decision problem X , its complement X̄ is the same problem with“yes” and “no” answeres reversed.complement-SAT: Is φ always false?Ruta (UIUC)CS47345Spring 202145 / 55
NP vs co-NPNP: Problems with polynomial time verifier for a “yes” instance.SAT: Given a CNF formula φ, does there exists a satisfying assignment?- Poly-time verification (proof) for “yes” instances.DefinitionGiven a decision problem X , its complement X̄ is the same problem with“yes” and “no” answeres reversed.complement-SAT: Is φ always false?- Poly-time verification (proof) for “no” instances.Ruta (UIUC)CS47345Spring 202145 / 55
NP vs co-NPNP: Problems with polynomial time verifier for a “yes” instance.SAT: Given a CNF formula φ, does there exists a satisfying assignment?- Poly-time verification (proof) for “yes” instances.DefinitionGiven a decision problem X , its complement X̄ is the same problem with“yes” and “no” answeres reversed.complement-SAT: Is φ always false?- Poly-time verification (proof) for “no” instances.co-NP: Complements of decision problems in NP.No-Independent-Set, Is-Prime, No-Clique.Ruta (UIUC)CS47345Spring 202145 / 55
NP vs co-NPNP: Problems with polynomial time verifier for a “yes” instance.SAT: Given a CNF formula φ, does there exists a satisfying assignment?- Poly-time verification (proof) for “yes” instances.DefinitionGiven a decision problem X , its complement X̄ is the same problem with“yes” and “no” answeres reversed.complement-SAT: Is φ always false?- Poly-time verification (proof) for “no” instances.co-NP: Complements of decision problems in NP.No-Independent-Set, Is-Prime, No-Clique.Poly-time verification for “no” instances“no” instances can be solved in non-deterministic po
2;:::x n. 1 A literal is either a boolean variable x i or its negation :x i. 2 A clause is a disjunction of literals. For example, x 1 _x 2 _:x 4 is a clause. 3 A formula in conjunctive normal form (CNF) is propositional formula which is a conjunction of clauses 1 (x 1 _x 2_:x 4) (x _:x 3) x 5 is a CNF formula. 4 A formula 'is a 3CNF:
