# jemdoc: addcss{rbh.css}, addcss{jacob.css} = p vs np ~~~ {}{raw} history   P   NP   NP-C   sat   21 others   sat->3sat   3sat->IS   longest path   clique   wc time   ~~~ ~~~ {}{raw}

complexity theory: history

~~~ ~~~ - [http://aleph0.clarku.edu/~djoyce/hilbert/ 1900 Hilbert 23 problems] - [https://en.wikipedia.org/wiki/Millennium_Prize_Problems 2000 Clay 7 problems] - [https://simple.wikipedia.org/wiki/P_versus_NP P = NP? simple.wiki] - [https://en.wikipedia.org/wiki/Bombe Turing et al Bombe] - [https://en.wikipedia.org/wiki/Colossus_computer Colossus] - [https://en.wikipedia.org/wiki/ENIAC ENIAC] - [https://en.wikipedia.org/wiki/Blossom_algorithm blossoms] - [http://www.math.uiuc.edu/documenta/vol-ismp/34_pulleyblank-william.pdf good algorithm] ~~~ ~~~ {}{raw}

class P

~~~ ~~~ - decision problem: answer yes or no -- e.g. here is a graph, is there a path between A,B with distance at most 31? -- e.g. here is a graph, does it have a clique of size 32? -- e.g. here is a CNF formula, is it satisfiable? - class P: set of decision problems that can be solved in polytime -- e.g. at-most-k distance problem: given a graph G, nodes A,B, integer k, is there a path between A,B with distance at most k? -- above usually called shortest path problem, so we say +shortest path is in P+ - not known: -- k-clique in P ? -- sat (satisfiability) in P ? ~~~ ~~~ {}{raw}

class NP

~~~ ~~~ - decision problem yes(no)-instance: instance of problem where answer is yes(no) - class NP -- decision problem -- for every yes-instance, exists yes-proof (proof that answer is yes) that can be verified in polytime - e.g. is sat in NP ? -- yes, because -- consider a yes instance, i.e. a satisfiable formula -- it must have a satisfying assignment -- so a yes-proof for sat is a satisfying assignment -- if someone gives you a formula in CNF, and an assignment, how long does it take you to verify that this assignment satisfies the formula? -- you assign truth values to the n variables, time O(n) -- for each clause, you check that the assignment is satisfied, time O(nm) -- so in O(nm) time you can verify that the formula is satisfiable -- so sat is in NP ~~~ ~~~ {}{raw}

class NP-C

~~~ ~~~ - class NP-C: NP-complete problems -- informally, each problem in NP-C is as hard as any problem in NP -- formally, a problem X in NP is +complete+ if, for each problem A in NP, there is a polytime process that --- takes an instance a of A --- converts it into an instance x of X --- preserves yes-answers: answer(a) is yes if and only if answer(x) is yes - consequence -- suppose exists polytime algorithm for some such X -- then any problem in NP can be solved in polytime - above consequence is why we say NP-C are hardest problems in NP ~~~ ~~~ {}{raw}

sat NP-C

~~~ ~~~ - 1971 (Cook) CNF-sat is NP-complete. - [https://en.wikipedia.org/wiki/Cook-Levin_theorem Cook-Levine theorem and proof] - unrestricted sat is a generalization of CNF-sat, and also in NP, so unrestricted sat is also NP-complete - transform from sat to cnf-sat with [https://en.wikipedia.org/wiki/Conjunctive_normal_form Tseitin's method] - transform from cnf-sat to 3-sat (at most 3, or exact 3) [https://cse.iitkgp.ac.in/~palash/2018AlgoDesignAnalysis/SAT-3SAT.pdf like this] - transform from exact-3-sat to 3-coloring [https://cgi.csc.liv.ac.uk/~igor/COMP309/3CP.pdf like this] ~~~ ~~~ {}{raw}

21 others NP-C

~~~ ~~~ - suppose we want to show problem X is NP-complete (so, hard) - what can we do ? -- 1) show X is in NP -- 2) show that some NP-complete problem C can be poly-transformed into X, so that answers (yes/no) are same for C instance and transformed X instance -- 3) then we have shown X is NP-complete. why ? -- because any problem T in NP can be transformed into sat, and then into X -- so if we could solve X in poly T, we could solve T in poly time - 1972 (Karp) 21 problems NP-C: -- 3-sat (each clause has {{≤}} 3 literals) -- clique -- knapsack -- set cover -- {{...}} - [https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems Karp's 21 reductions] ~~~ ~~~ {}{raw}

sat reduces to 3-sat

~~~ ~~~ {example reduction}{} consider an instance of sat: [ 1 2 3 -4 -6 ] [ 1 2 -3 -5 ] [ 1 -2 3 -5 -6 ] [ 1 3 4 ] [ 2 -3 4 -6 ] replace each long clause with equivalent set of 3-literal clauses [ 1 2 3 -4 -6] => [ 1 2 10] [-10 3 11] [-11 -4 -6] [ 1 2 -3 -5] => [ 1 2 12] [-12 -3 -5] [ 1 -2 3 -5 -6] => [ 1 -2 13] [-13 3 14] [-14 -5 -6] [ 2 -3 4 -6] => [ 2 -3 15] [-15 4 -6] corresponding instance of 3-sat [ 1 2 10 ] [ -10 3 11 ] [ -11 -4 -6 ] [ 1 2 12 ] [ -12 -3 -5 ] [ 1 -2 13 ] [ -13 3 14 ] [ -14 -5 -6 ] [ 1 3 4 ] [ 2 -3 15 ] [ -15 4 -6 ] ~~~ ~~~ {above reduction implies 3-sat is NP-C} - number literals in new instance < 3 times original, so reduction polytime - reduction maps yes-instance to yes-intance, no-instance to no-instance - by Cook's theorem -- sat is NP-C -- so any instance t of problem T in NP can be polytime reduced to instance s of sat, with answer preserved - as above, instance s can be polytime reduced to instance u of 3-sat, with answer preserved - so t can be polytime reduced to u, with answer preserved - so polysolving 3-sat implies polysolving T, for every T in NP - so 3-sat is NP-complete ~~~ ~~~ {clique and independent set} - [https://en.wikipedia.org/wiki/Clique_(graph_theory) clique] in a graph, set of nodes, each pair adjacent - [https://en.wikipedia.org/wiki/Independent_set_(graph_theory) independent set] in a graph, set of nodes, each pair non-adjacent - independent set decision problem: given a graph G and an integer k, does G have an independent set of size k ? - clique decision problem: given a graph G and an integer k, does G have a clique of size k ? ~~~ ~~~ {}{raw}

3-sat reduces to ind. set

~~~ ~~~ {example reduction} - consider an instance of 3-sat - each clause with t literals becomes clique with t nodes - e.g. clause {{[ a b -c ]}} becomes clique \{a b -c\} - for each literal pair x,-x from different clauses, add edge in graph - e.g. what is graph reduced from this CNF formula? {{[-1 2 -3] [ 1 -2 3] [ 1 2 3] [-1 2]}} ~~~ ~~~ {} {{independent set reduction}} ~~~ ~~~ {claim: formula satisfiable iff graph has m-independent set} - assume formula satisfiable, say with assignment A -- in each clause, at least one literal true -- in graph, pick one true node from each clause -- picked nodes form independent set (why?) -- so graph has m-ind set - assume graph has m-ind set -- set has exactly one node in each clauseclique -- set corresponding literal true -- cannot have both x and -x true (why?) -- each clause satisfied by this assignment ~~~ ~~~ {consequence of claim ?} - independent set is NP-C :) - why ? ~~~ ~~~ {exercise} show independent set reduces to clique ~~~ ~~~ {consequence of exercise ?} - clique is NP-C :) - why ? ~~~ ~~~ {}{raw}

longest path

~~~ ~~~ - *longest path* ~ given graph G, find a longest path - how hard is longest path ? - longest path not in NP (not a yes/no question) - decision version of longest path ? - *k-path* ~ given graph G and integer k, does G have path with {{≥ k}} nodes? - *Hamiltonian path* ~ given graph G, does G have path with all nodes? - *Hamiltonian cycle* ~ given graph G, does G have cycle with all nodes? - H-cycle is in NP-C: Karp's reduction from [http://cs.indstate.edu/~bdhome/HamCycle.pdf vertex cover] - can you prove that H-path is NP-C ? - proof: reduction from H-cycle. ~ let G be input to H-cycle. ~ for each edge (x,y) of G, construct graph G(x,y) as follows: -- remove edge (x,y) -- add new node w, adjacent only to x -- add new node z, adjacent only to y - claim: G has H-cycle through edge (x,y) iff G(x,y) has H-path - so G has H-cycle iff at least one G(x,y) has H-path - so assume H-path is in P - use some such alg on each graph G(x,y) - so, in this way, if we can solve H-path in time {{O(nt)}} for fixed t, we can solve H-cycle in time {{O(nt+2)}} - so we have proved that H-path is in NP-C - this {{H-cycle->H-path}} reduction, with multiple calls to the target algorithm, is called a *Cook* reduction - other reductions we have seen, with 1 call to target algorithm, are called *Karp* reductions - a problem is *NP-hard* if it is as hard as some NP-C problem, but not necessarily in NP - longest path is NP-hard ~~~ ~~~ {}{raw}

brute force k-clique time

~~~ ~~~ - try each k-subset -- (n choose k) = ${\Large\mathbf{n \choose k}}$ {{= n! / (k!) (n-k)! = n(n-1)...(n-(k-1)) / k!}} subsets -- checking each takes {{Θ(k2)}} time - if k constant, {{Θ(nk)}} subsets, total WC time {{Θ(k2 nk) = Θ(nk)  }} polynomial :) - here, WC time polynomial :) - if k not constant, e.g. can grow with n ? -- largest (n choose k) ? when {{k = n/2}} (CMPUT 272) -- how big is (n choose n/2) ? -- {{  n!   ≈   √  2 π n  (n/e)n   }} (Stirling) -- better: {{4^n/(sqrt(pi*(n+1/3))) <= (2n choose n) <= 4^n/(sqrt(pi*(n+1/4)))}} -- so (n choose n/2) grows --- slower than {{2^n}} --- faster than {{(2-eps)^n}}, for any positive epsilon - try each subset, worst case runtime {{Θ(   n1.5 2n   )}} - here, WC time exponential :( ~~~ ~~~ {1000 choose 500}{} 2.7035582144 e+299 Stirling approx 2.7028824093 e+299 better " 2.7028824095 e+299 exact (rounded) ~~~ ~~~ {}{raw}

wc time for some NP-C problems

~~~ ~~~ - brute force clique, also independent set -- {{Θ(   n1.5 2n   )}} - knapsack, n items, each value/wt n bits, capacity .5 total wt, input size {{t = Θ( n2 )}} -- {{Θ( n2 2n )   =   Θ( t 2√ t )}} - brute force set cover, m subsets of an n-set -- {{Θ( n 2m )}} - brute force sat, total m literals, n variables -- {{Θ( m 2n )}} ~~~