Transcription
CS 473: Algorithms, Spring 2018SAT, NP, NP-CompletenessLecture 22April 13, 2018Most slides are courtesy Prof. ChekuriRuta (UIUC)CS4731Spring 20181 / 57
Part IReductions ContinuedRuta (UIUC)CS4732Spring 20182 / 57
II: Partition and subset sum?Problem: PartitionProblem: Subset SumInstance: A set S of nnumbers.Question: Is thereP a subsett T t P T S s.t.s?s S\TInstance: S - set of positiveintegers,t: - an integer number(target).Question: Is thereP a subsetX S such that x X x t?Assume that we can solve Partition in polynomial time, then we cansolve Subset Sum in polynomial time. This statement is(A) True.(B) Mostly true.(C) False.(D) Mostly false.Ruta (UIUC)CS4733Spring 20183 / 57
Polynomial Time ReductionKarp reductionX P Y : algorithm A reduces problem X to problem Y inpolynomial-time:1given an instance IX of X , A produces an instance IY of Y2A runs in time poly ( IX ) IY poly ( IX )3Answer to IX YES iff answer to IY is YES.Ruta (UIUC)CS4734Spring 20184 / 57
Polynomial Time ReductionKarp reductionX P Y : algorithm A reduces problem X to problem Y inpolynomial-time:1given an instance IX of X , A produces an instance IY of Y2A runs in time poly ( IX ) IY poly ( IX )3Answer to IX YES iff answer to IY is YES.Consequences:poly-time algorithm for Y poly-time algorithm for X .X is “hard” Y is “hard”.Ruta (UIUC)CS4734Spring 20184 / 57
Polynomial Time ReductionKarp reductionX P Y : algorithm A reduces problem X to problem Y inpolynomial-time:1given an instance IX of X , A produces an instance IY of Y2A runs in time poly ( IX ) IY poly ( IX )3Answer to IX YES iff answer to IY is YES.Consequences:poly-time algorithm for Y poly-time algorithm for X .X is “hard” Y is “hard”.Note. X P YRuta (UIUC) 6Y P XCS4734Spring 20184 / 57
A More General ReductionTuring ReductionDefinition (Turing reduction.)Problem X polynomial time reduces to Y if there is an algorithm Afor X that has the following properties:1on any given instance IX of X , A uses polynomial in IX “steps”2a step is either a standard computation step, or3a sub-routine call to an algorithm that solves Y .This is a Turing reduction.Ruta (UIUC)CS4735Spring 20185 / 57
A More General ReductionTuring ReductionDefinition (Turing reduction.)Problem X polynomial time reduces to Y if there is an algorithm Afor X that has the following properties:1on any given instance IX of X , A uses polynomial in IX “steps”2a step is either a standard computation step, or3a sub-routine call to an algorithm that solves Y .This is a Turing reduction.Note: In making sub-routine call to algorithm to solve Y , A can onlyask questions of size polynomial in IX . Why?Ruta (UIUC)CS4735Spring 20185 / 57
Comparing reductions1Karp reduction:IXReductionyesIYSolver for YnoSolver for X2Turing reduction:IXyesTuring reductionAlgorithmnoSolver for YRuta (UIUC)12CS473Algorithm to solve X cancall solver for Ypoly ( Ix ) many times.Input to every call is ofsize poly ( Ix ).6Spring 20186 / 57
Example of Turing ReductionProblem (Independent set in circular arcs graph.)Input: Collection of arcs on a circle.Goal: Compute the maximum number of non-overlapping arcs.Reduced to the following problem:?Problem (Independent set of intervals.)Input: Collection of intervals on the line.Goal: Compute the maximum number of non-overlapping intervals.How?Ruta (UIUC)CS4737Spring 20187 / 57
Example of Turing ReductionProblem (Independent set in circular arcs graph.)Input: Collection of arcs on a circle.Goal: Compute the maximum number of non-overlapping arcs.Reduced to the following problem:?Problem (Independent set of intervals.)Input: Collection of intervals on the line.Goal: Compute the maximum number of non-overlapping intervals.How? Used algorithm for interval problem multiple times.Ruta (UIUC)CS4737Spring 20187 / 57
Turing vs Karp Reductions12345Turing reductions more general than Karp reductions.Turing reduction useful in obtaining algorithms via reductions.Karp reduction is simpler and easier to use to prove hardness ofproblems.Perhaps surprisingly, Karp reductions, although limited, sufficefor most known NP-Completeness proofs.Karp reductions allow us to distinguish between NP and co-NP(more on this later).Ruta (UIUC)CS4738Spring 20188 / 57
Part IIThe Satisfiability Problem (SAT)Ruta (UIUC)CS4739Spring 20189 / 57
Propositional FormulasDefinitionConsider a set of boolean variables x1 , x2 , . . . xn .1A literal is either a boolean variable xi or its negation xi .Ruta (UIUC)CS47310Spring 201810 / 57
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)CS47310Spring 201810 / 57
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)CS47310Spring 201810 / 57
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)CS47310Spring 201810 / 57
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)CS47311Spring 201811 / 57
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)CS47312Spring 201812 / 57
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)CS47313Spring 201813 / 57
3SAT P SAT123SAT P SAT.Because.A 3SAT instance is also an instance of SAT.Ruta (UIUC)CS47314Spring 201814 / 57
SAT P 3SATClaimSAT P 3SAT.Ruta (UIUC)CS47315Spring 201815 / 57
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)CS47315Spring 201815 / 57
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)CS47316Spring 201816 / 57
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)CS47316 Spring 201816 / 57
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)CS47316Spring 201816 / 57
What about 2SAT?Ruta (UIUC)CS47317Spring 201817 / 57
What about 2SAT?2SAT can be solved in polynomial time! (specifically, linear time!)Ruta (UIUC)CS47317Spring 201817 / 57
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)CS47317Spring 201817 / 57
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)CS47317Spring 201817 / 57
What about 2SAT?A challenging exercise: Given a 2SAT formula show to compute itssatisfying assignment.Look in books etc.Ruta (UIUC)CS47318Spring 201818 / 57
Independent SetProblem: Independent SetInstance: A graph G, integer k.Question: Is there an independent set in G of size k?Ruta (UIUC)CS47319Spring 201819 / 57
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)CS47319Spring 201819 / 57
Part IIIDefinition of P and NPRuta (UIUC)CS47320Spring 201820 / 57
Recap . . .Problems12345Independent SetVertex CoverSet CoverSAT3SATRuta (UIUC)CS47321Spring 201821 / 57
Recap . . .Problems12345Independent SetVertex CoverSet CoverSAT3SATRelationship3SAT P Independent SetRuta (UIUC)CS47321Spring 201821 / 57
Recap . . .Problems12345Independent SetVertex CoverSet CoverSAT3SATRelationship P3SAT P Independent Set P Vertex CoverRuta (UIUC)CS47321Spring 201821 / 57
Recap . . .Problems12345Independent SetVertex CoverSet CoverSAT3SATRelationship P3SAT P Independent Set P Vertex Cover P Set CoverRuta (UIUC)CS47321Spring 201821 / 57
Recap . . .Problems12345Independent SetVertex CoverSet CoverSAT3SATRelationship P3SAT P Independent Set P Vertex Cover P Set Cover3SAT P SAT P 3SATRuta (UIUC)CS47321Spring 201821 / 57
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(Ix ) ”yes” iff Ix X .A is said to have a polynomial running time if there is apolynomial p(·) such that for every string Ix , A(Ix ) terminatesin at most O(p( Ix )) steps.Ruta (UIUC)CS47322Spring 201822 / 57
Deterministic Turing MachineP (polynomial-time): problems that deterministic TM solves inpolynomial time.Ruta (UIUC)CS47323Spring 201823 / 57
Nondeterministic Turing MachineNP (nondeterministic polynomial time): problems thatnondeterministc TM solves in polynomial time.Ruta (UIUC)CS47324Spring 201824 / 57
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)CS47325Spring 201825 / 57
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)CS47325Spring 201825 / 57
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)CS47326Spring 201826 / 57
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)CS47327Spring 201827 / 57
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)CS47327Spring 201827 / 57
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)CS47327Spring 201827 / 57
CertifiersDefinitionAn algorithm C (·, ·) is a certifier for problem X if for every Ix Xthere is some string t such that C (Ix , t) ”yes”, and conversely, iffor some Ix and t, C (Ix , t) ”yes” then Ix X .The string t is called a certificate or proof for s.Ruta (UIUC)CS47328Spring 201828 / 57
CertifiersDefinitionAn algorithm C (·, ·) is a certifier for problem X if for every Ix Xthere is some string t such that C (Ix , t) ”yes”, and conversely, iffor some Ix and t, C (Ix , t) ”yes” then Ix X .The string t is called a certificate or proof for s.Definition (Efficient Certifier.)A certifier C is an efficient certifier for problem X if there is apolynomial p(·) such that for every string s, we have that? Ix X if and only if? there is a string t:123 t p( Ix ),C (Ix , t) ”yes”,and C runs in polynomial time in Ix .Ruta (UIUC)CS47328Spring 201828 / 57
Example: Independent Set1Problem: Does G (V , E ) have an independent set of size k?12Certificate: Set S V .Certifier: Check S k and no pair of vertices in S isconnected by an edge.Ruta (UIUC)CS47329Spring 201829 / 57
Example: Vertex Cover1Problem: Does G have a vertex cover of size k?Ruta (UIUC)CS47330Spring 201830 / 57
Example: Vertex Cover1Problem: 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)CS47330Spring 201830 / 57
Example: SAT1Problem: Does formula ϕ have a satisfying truth assignment?Ruta (UIUC)CS47331Spring 201831 / 57
Example: SAT1Problem: 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)CS47331Spring 201831 / 57
Example: CompositesProblem: CompositeInstance: A number s.Question: Is the number s a composite?Ruta (UIUC)CS47332Spring 201832 / 57
Example: CompositesProblem: CompositeInstance: A number s.Question: Is the number s a composite?1Problem: Composite.12Certificate: A factor t s such that t 6 1 and t 6 s.Certifier: Check that t divides s.Ruta (UIUC)CS47332Spring 201832 / 57
Not composite?Problem: Not CompositeInstance: A number s.Question: Is the number s not a composite?The problem Not Composite is(A) Can be solved in linear time.(B) in P.(C) Can be solved in exponential time.(D) Does not have a certificate or an efficient certifier.(E) The status of this problem is still open.Ruta (UIUC)CS47333Spring 201833 / 57
Nondeterministic Polynomial TimeAlternate definitionDefinitionNondeterministic Polynomial Time (denoted by NP) is the class ofall problems that have efficient certifiers.Ruta (UIUC)CS47334Spring 201834 / 57
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)CS47334Spring 201834 / 57
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)CS47335Spring 201835 / 57
P versus NPPropositionP NP.Ruta (UIUC)CS47336Spring 201836 / 57
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)CS47336Spring 201836 / 57
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)CS47337Spring 201837 / 57
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 ), .Ruta (UIUC)CS47337Spring 201837 / 57
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)CS47338Spring 201838 / 57
Examples123SAT: try all possible truth assignment to variables.Independent Set: try all possible subsets of vertices.Vertex Cover: try all possible subsets of vertices.Ruta (UIUC)CS47339Spring 201839 / 57
Is NP efficiently solvable?We know P NP EXP.Ruta (UIUC)CS47340Spring 201840 / 57
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)CS47340Spring 201840 / 57
If P NP . . .Or: If pigs could fly then life would be sweet.1Many important optimization problems can be solved efficiently.Ruta (UIUC)CS47341Spring 201841 / 57
If P NP . . .Or: If pigs could fly then life would be sweet.12Many important optimization problems can be solved efficiently.The RSA cryptosystem can be broken.Ruta (UIUC)CS47341Spring 201841 / 57
If P NP . . .Or: If pigs could fly then life would be sweet.123Many important optimization problems can be solved efficiently.The RSA cryptosystem can be broken.No security on the web.Ruta (UIUC)CS47341Spring 201841 / 57
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)CS47341Spring 201841 / 57
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)CS47341Spring 201841 / 57
If P NP this implies that.(A)(B)(C)(D)Vertex Cover can be solved in polynomial time.P EXP.EXP P.All of the above.Ruta (UIUC)CS47342Spring 201842 / 57
P versus NPStatusRelationship 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)CS47343Spring 201843 / 57
Part IVNP-Completeness and Cook-LevinTheoremRuta (UIUC)CS47344Spring 201844 / 57
“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)CS47345Spring 201845 / 57
NP-Complete ProblemsDefinitionA problem X is said to be NP-Hard if1(Hardness) For any Y NP, we have that Y P X.Ruta (UIUC)CS47346Spring 201846 / 57
NP-Complete ProblemsDefinitionA problem X is said to be NP-Hard if1(Hardness) For any Y NP, we have that Y P X.DefinitionA problem X is said to be NP-Complete if1X NP, and2X is NP-HardRuta (UIUC)CS47346Spring 201846 / 57
NP-Complete ProblemsDefinitionA problem X is said to be NP-Hard if1(Hardness) For any 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)CS47346Spring 201846 / 57
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)CS47347Spring 201847 / 57
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)CS47347Spring 201847 / 57
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)CS47347Spring 201847 / 57
Consequences of proving NP-CompletenessIf X is NP-Complete1Since we believe P 6 NP,2and solving X implies P NP.X is unlikely to be efficiently solvable.Ruta (UIUC)CS47348Spring 201848 / 57
Consequences of proving NP-CompletenessIf X is NP-Complete1Since we believe P 6 NP,2and solving X 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)CS47348Spring 201848 / 57
Consequences of proving NP-CompletenessIf X is NP-Complete1Since we believe P 6 NP,2and solving X 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)CS47348Spring 201848 / 57
Consequences of proving NP-CompletenessIf X is NP-Complete1Since we believe P 6 NP,2and solving X 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)CS47348Spring 201848 / 57
NP-Complete ProblemsQuestionAre there any problems that are NP-Complete?AnswerYes! Many, many problems are NP-Complete.Ruta (UIUC)CS47349Spring 201849 / 57
Cook-Levin TheoremTheoremSAT is NP-Complete.Ruta (UIUC)CS47350Spring 201850 / 57
Cook-Levin TheoremTheoremSAT is NP-Complete.Using reductions one can prove that many other problems areNP-CompleteRuta (UIUC)CS47350Spring 201850 / 57
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)CS47351Spring 201851 / 57
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)CS47351Spring 201851 / 57
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)CS47351Spring 201851 / 57
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)CS47352Spring 201852 / 57
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)CS47352Spring 201852 / 57
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)CS47353Spring 201853 / 57
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)CS47353Spring 201853 / 57
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)CS47353Spring 201853 / 57
Interpreting 3SATThere are two ways to think about 3SATRuta (UIUC)CS47354Spring 201854 / 57
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)CS47354Spring 201854 / 57
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)CS47354Spring 201854 / 57
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)CS47354Spring 201854 / 57
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)CS47355Spring 201855 / 57
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)CS47355Spring 201855 / 57
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)CS47355Spring 201855 / 57
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)CS47355Spring 201855 / 57
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 l
Part II The Satis ability Problem (SAT) Ruta (UIUC) CS473 9 Spring 2018 9 / 57. Propositional Formulas De nition Consider a set of boolean variables x 1;x 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
