Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9NP Complete Problem: hardest problem in NPSlide 11Slide 12NP-Complete Problems3SATSlide 15Slide 16How to prove?Slide 18Polynomial Time ReductionSlide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Independent SetSlide 30Key ObservationSlide 32Slide 33Vertex Cover is NP CompleteK-Indep Set P Vertex CoverSlide 36Other NP-Complete ProblemsOther Problems in NPFORMAL LANGUAGES, AUTOMATA AND COMPUTABILITY15-453NP = NTIME(nk)k  NTheorem: L  NP  if there exists a poly-time Turing machine V(erifier) withL = { x | y(witness) |y| = poly(|x|) and V(x,y) accepts }Proof:(1) If L = { x | y |y| = poly(|x|) and V(x,y) accepts } then L  NPBecause we can guess y and then run V(2) If L  NP thenL = { x | y |y| = poly(|x|) and V(x,y) accepts } Let N be a non-deterministic poly-time TM that decides L and define V(x,y) to accept if y is an accepting computation history of N on xA language is in NP if and only if there exist polynomial-length certificates for membership to the languageSAT is in NP because a satisfying assignment is a polynomial-length certificate that a formula is satisfiableNP = all the problems for which once you have the answer it is easy (i.e. efficient) to verifyP = NP?If P = NP…Cryptography as we know it would not be possible (e.g. RSA)Mathematicians would be out of a jobAI program become perfect as exhaustive search is efficientIf P = NP…Writing symphonies is as easy as listening to them.Being a chef is as easy as eating.Writing Shakespeare is as easy as recognizing Shakespeare.Generation is as easy as recognition:POLY-TIME REDUCIBILITYA language A is polynomial time reducible to language B, written A P B, if there is a polynomial time computable function f : Σ*  Σ*, where for every w,w  A  f(w)  Bf is called a polynomial time reduction of A to BNP Complete Problem: hardest problem in NPIntuitively, L is harder than L’ if L’ is polynomial reducible to L.NP Complete Problem: If such a problem has an efficient algorithm (in P), then every other problem also has efficient algorithm.Theorem (Cook-Levin): SAT is NP-completeCorollary: SAT  P if and only if P = NPPNPSAT Any thing in NP P 3SATYou can think of -> as “easier than”. SAT is the hardest problem in NP.NP-Complete Problems•3SAT•k-Clique•Vertex Cover•Independent Set3SAT•Problem: Given a CNF where each clause has 3 variables, decide whether it is satisfiable or not.•(x1  x1  x2)  (x1  x2  x2)  (x1  x2  x2)3SAT ={  | y such that y is a satisfying assigment to  and  is in 3cnf } 3SAT is NP CompleteHow about 2SAT?PNP3SATSAT What we want to prove?How to prove?1. We can convert (in polynomial time) a given SAT instance S into a 3SAT instance S’ such that•If S is satisfiable, then S’ is satisfiable.•If S’ is satisfiable, then S is satisfiable.Key Observationx1  x2  x3  x4  x5 is satisfiable if and only if(x1  x2  z1) (  z1  x3  z2 )( z2  x4  z3) ( z3  x4  x5)is satisfiable.Polynomial Time ReductionClause in SATx1x1   x2x1  x2  x3x1  x2  x3  x4x1  x2  x3  x4  x5Clauses in 3SATx1  x1  x1x1  x1   x2x1  x2  x3(x1  x2  z1) (  z1  x3  x4)(x1  x2  z1) (  z1  x3  z2)( z2  x4  z3) ( z3 x4  x5)CLIQUE baecdfgk-clique = complete subgraph of k nodesK-CliquesA K-clique is a set of K nodes with all K(K-A K-clique is a set of K nodes with all K(K-1)/2 possible edges between them1)/2 possible edges between themThis graph contains a 4-cliqueCLIQUE = { (G,k) | G is an undirected graph with a k-clique }Theorem: CLIQUE is NP-Complete(1) CLIQUE  NP(2) 3SAT P CLIQUEAssume a reasonable encoding of graphs (example: the adjacency matrix is reasonable)Brute Force Algorithm: Try out all {n choose k} possible locations for the Try out all {n choose k} possible locations for the k cliquek cliquePNPCLIQUE3SATCLIQUE is NP-Complete3SAT P CLIQUEWe transform a 3-cnf formula  into (G,k) such that  3SAT  (G,k)  CLIQUEThe transformation can be done in time that is polynomial in the length of 3SAT P CLIQUEWe transform a 3-cnf formula  into (G,k) such that  3SAT  (G,k)  CLIQUEIf  has m clauses, we create a graph with m clusters of 3 nodes each, and set k=mEach cluster corresponds to a clause. Each node in a cluster is labeled with a literal from the clause.We do not connect any nodes in the same clusterWe connect nodes in different clusters whenever they are not contradictory(x1  x1  x2)  (x1  x2  x2)  (x1  x2  x2) x1x1x1x2x2x2x2x2x1k = #clausesclause#nodes = 3(# clauses)(x1  x1  x1)  (x1  x1  x2)  (x2  x2  x2)  (x2  x2  x1) x1x1x2x2x1x1x2x2x1x2x2x1This graph contains an independent set of size 3Independent SetAn An independent set independent set is a set of nodes with no is a set of nodes with no edges between themedges between themIndependent SetG(V,E)Problem: Given a graph G and k, is there a size k independent set?Complement of GGiven a graph G, let G*, the complement of G, be the graph such that two nodes are connected in G* if and only if the corresponding nodes are not connected in G GG*Key Observation•For a graph G, vertex set S is an independent set if and only if S is clique in G*.Let G be an n-node graphIs there size clique in G?Is there size k independent set in G*?VERTEX COVERbaecdbaecdvertex cover = set of nodes that cover all edgesVertex Cover is NP Complete •Given a Graph G(V,E), decide if there is k vertex such that every edge is covered by one of them?K-Indep Set P Vertex CoverKey Observation•For a graph G(V,E), S is a independent set if and only if V-S is a vertex cover.Other NP-Complete Problems•Travelling Salesman Problem•Hamiltonian Path•Max Cut•Subset Sum•Integer Programming•….Other Problems in NP •Graph Isomorphism•Factoring NumberWe don’t know if they are NP Complete or