Ch.14: NP-Complete Problems

Week 14 of the book "Automata, Formal Languages, and Turing Machines" by Emre Sermutlu (2020) 14.1. P versus NP 14.2. Polynomial Time Reductions 14.3. NP-Complete Problems

69 flashcards · Computer Science · by lakesare

Part of Textbooks › Automata, Formal Languages, and Turing Machines (Emre Sermutlu) · 14 courses

  1. [P versus NP] What are the complexity classes P\mathcal{P}P and NP\mathcal{NP}NP ?

    P\mathcal{P}P The problems that have a polynomial time solution (a deterministic algorithm that solves the problem in polynomial time). Example: sorting nnn numbers takes O(nlog⁡n)O(n \log n)O(nlogn) steps. NP\mathcal{NP}NP The problems that have a polynomial time verifier (given a proposed solution, checking the solution takes polynomial time). Example: Hamiltonian Path: checking that a given sequence of vertices is a path that visits every vertex once takes polynomial time.

  2. [P versus NP] Why is every problem in P\mathcal{P}P also in NP\mathcal{NP}NP ?

    A polynomial time solution is also a polynomial time verifier: the verifier ignores the proposed solution and solves the problem. So P⊆NP\mathcal{P} \subseteq \mathcal{NP}P⊆NP .

  3. [P versus NP] Is it known whether P=NP\mathcal{P} = \mathcal{NP}P=NP ?

    No. It is unknown whether P=NP\mathcal{P} = \mathcal{NP}P=NP or P\mathcal{P}P is a proper subset of NP\mathcal{NP}NP . Many researchers consider the question the most important open problem in computer science. Stephen Cook gave its precise formulation in 1971. The two possibilities.

  4. [P versus NP] Graph Coloring, Vertex Cover, Hamiltonian Path, Traveling Salesman and Subset–Sum are in NP\mathcal{NP}NP . What would follow for these problems from P=NP\mathcal{P} = \mathcal{NP}P=NP , and what from P≠NP\mathcal{P} \ne \mathcal{NP}P=NP ?

    P=NP\mathcal{P} = \mathcal{NP}P=NP : all have polynomial time algorithms. P≠NP\mathcal{P} \ne \mathcal{NP}P=NP : none can be solved in polynomial time. Many experts expect P≠NP\mathcal{P} \ne \mathcal{NP}P=NP . Polynomial algorithms are known only for approximate solutions or for special cases.

  5. [P versus NP] Is every algorithm that is not polynomial time exponential time?

    No. A quasi-polynomial ( QPQPQP ) algorithm needs more steps than any polynomial but fewer than an exponential one. Example: nlog⁡2n=2(log⁡2n)2n^{\log_2 n} = 2^{(\log_2 n)^2}nlog2​n=2(log2​n)2 grows faster than every ncn^cnc and slower than 2n2^n2n .

  6. [Polynomial Time Reductions] When is problem YYY polynomial-time reducible to problem XXX , written Y⩽PXY \leqslant_P XY⩽P​X ?

    YYY can be solved using a polynomial number of computational steps and a polynomial number of calls to a solution method for XXX . Example: finding the second largest of nnn numbers ⩽P\leqslant_P⩽P​ sorting: sort once, then take the second number from the end.

  7. [Polynomial Time Reductions] In Y⩽PXY \leqslant_P XY⩽P​X , which of the two problems is the simpler one?

    YYY , the problem that is reduced. Here "reduce" means: assume a solution algorithm for the harder problem XXX and adapt the algorithm to the easier problem YYY . This is the opposite of the usual mathematical use of the word.

  8. [Polynomial Time Reductions] When is a language AAA polynomial-time reducible to a language BBB (alphabet Σ\SigmaΣ )?

    When a function f:Σ∗→Σ∗f : \Sigma^* \to \Sigma^*f:Σ∗→Σ∗ computable in polynomial time exists with s∈A ⟺ f(s)∈Bs \in A \iff f(s) \in Bs∈A⟺f(s)∈B for every s∈Σ∗s \in \Sigma^*s∈Σ∗ . Example: AAA = binary strings of even length, BBB = binary strings of odd length: f(s)=s1f(s) = s1f(s)=s1 (append one symbol).

  9. [Polynomial Time Reductions] AAA and BBB are languages with A⩽PBA \leqslant_P BA⩽P​B , and B∈PB \in \mathcal{P}B∈P . What follows?

    A∈P\boldsymbol{A \in \mathcal{P}}A∈P Decide s∈As \in As∈A by computing f(s)f(s)f(s) and running the polynomial algorithm for BBB on f(s)f(s)f(s) . Since ∣f(s)∣|f(s)|∣f(s)∣ is polynomial in ∣s∣|s|∣s∣ , the total time is a polynomial of a polynomial, so polynomial.

  10. [Polynomial Time Reductions] AAA and BBB are languages with A⩽PBA \leqslant_P BA⩽P​B , and A∉PA \notin \mathcal{P}A∈/P . What follows?

    B∉P\boldsymbol{B \notin \mathcal{P}}B∈/P Contrapositive of: A⩽PBA \leqslant_P BA⩽P​B and B∈PB \in \mathcal{P}B∈P give A∈PA \in \mathcal{P}A∈P .

  11. [Polynomial Time Reductions] A: given a list of integers, is there a duplicate? B: given a list of integers, find the minimum distance between two of them. How does A ⩽P\leqslant_P⩽P​ B work?

    Find the minimum distance; there is a duplicate exactly when the minimum distance is 0. Example: 3,7,3,123, 7, 3, 123,7,3,12 : minimum distance ∣3−3∣=0|3 - 3| = 0∣3−3∣=0 , so there is a duplicate.

  12. [Polynomial Time Reductions] A: given integers n,mn, mn,m , find gcd⁡(n,m)\gcd(n, m)gcd(n,m) . B: given integers n,mn, mn,m , find lcm⁡(n,m)\operatorname{lcm}(n, m)lcm(n,m) . Which of A ⩽P\leqslant_P⩽P​ B and B ⩽P\leqslant_P⩽P​ A hold, and why?

    Both, by gcd⁡(n,m)⋅lcm⁡(n,m)=n⋅m\gcd(n, m) \cdot \operatorname{lcm}(n, m) = n \cdot mgcd(n,m)⋅lcm(n,m)=n⋅m . Example: gcd⁡(4,6)=2\gcd(4, 6) = 2gcd(4,6)=2 , lcm⁡(4,6)=12\operatorname{lcm}(4, 6) = 12lcm(4,6)=12 , and 2⋅12=24=4⋅62 \cdot 12 = 24 = 4 \cdot 62⋅12=24=4⋅6 .

  13. [Polynomial Time Reductions] A: binary strings that start and end with 1. B: binary strings that start and end with the same symbol. How does A ⩽P\leqslant_P⩽P​ B work?

    s∈As \in As∈A exactly when sss starts with 1 and s∈Bs \in Bs∈B : check the first symbol, then call the solution for B once. Example: 100110011001 starts with 1 and 1001∈B1001 \in B1001∈B , so 1001∈A1001 \in A1001∈A ; 0110∈B0110 \in B0110∈B but starts with 0, so 0110∉A0110 \notin A0110∈/A .

  14. [Polynomial Time Reductions] A: binary palindromes. B: binary strings that start and end with the same symbol. B is the simpler problem. Why does A ⩽P\leqslant_P⩽P​ B still hold?

    Call B on sss , delete the first and last symbol, and repeat: sss is a palindrome exactly when every call says yes. That is O(n)O(n)O(n) calls, a polynomial number. Example: 10101→010→110101 \to 010 \to 110101→010→1 : every call says yes, so 101011010110101 is a palindrome.

  15. [Polynomial Time Reductions] What is the Hamiltonian Cycle Problem (HCP)?

    Given an undirected graph GGG , is there a cycle that visits every vertex exactly once?

  16. [Polynomial Time Reductions] What is the decision version of the Traveling Salesman Problem (TSP)?

    Given a weighted graph GGG and a positive number kkk , is there a cycle that visits each vertex once and has total weight ≤k\le k≤k ?

  17. [Polynomial Time Reductions] How is a Hamiltonian Cycle Problem on a graph GGG with nnn vertices turned into a Traveling Salesman Problem (HCP ⩽P\leqslant_P⩽P​ TSP)?

    Join every two vertices; give weight 1 to the edges of GGG and weight 2 to the other pairs. Set k=nk = nk=n . A cycle through all nnn vertices has nnn edges of weight at least 1, so weight ≤n\le n≤n holds exactly when every edge has weight 1, i.e. the cycle is a Hamiltonian cycle of GGG . Left: GGG . Right: the weighted complete graph (dashed = weight 2). ACDBEAACDBEAACDBEA has weight 5=n5 = n5=n .

  18. [Polynomial Time Reductions] What is the Subset–Sum Problem?

    Given a set SSS of integers and a target number TTT : is there a subset of SSS that adds up to TTT ? Example: S={−20,−5,0,4,7,19}S = \{-20, -5, 0, 4, 7, 19\}S={−20,−5,0,4,7,19} , T=14T = 14T=14 : yes, 19+(−5)=1419 + (-5) = 1419+(−5)=14 .Example: S={−3,8,17,25,66}S = \{-3, 8, 17, 25, 66\}S={−3,8,17,25,66} , T=60T = 60T=60 : no; without 66 the largest sum is 505050 , and with 66 every sum is at least 636363 .

  19. [Polynomial Time Reductions] What is the Exact–Cover Problem?

    Given a set EEE and a set PPP of subsets of EEE : is there a collection of sets from PPP such that each element of EEE is in exactly one of them? Example: E={1,2,3,4,5}E = \{1, 2, 3, 4, 5\}E={1,2,3,4,5} , P={{2},{1,2},{2,3},{3,4,5},{1,2,3,4}}P = \{\{2\}, \{1,2\}, \{2,3\}, \{3,4,5\}, \{1,2,3,4\}\}P={{2},{1,2},{2,3},{3,4,5},{1,2,3,4}} : yes, {1,2},{3,4,5}\{1,2\}, \{3,4,5\}{1,2},{3,4,5} .

  20. [Polynomial Time Reductions] E={1,2,3,4,5}E = \{1, 2, 3, 4, 5\}E={1,2,3,4,5} , P={{2},{3},{1,2},{2,3},{3,4},{1,3,5}}P = \{\{2\}, \{3\}, \{1,2\}, \{2,3\}, \{3,4\}, \{1,3,5\}\}P={{2},{3},{1,2},{2,3},{3,4},{1,3,5}} . Is there an exact cover of EEE by sets from PPP ?

    No. Only {1,3,5}\{1,3,5\}{1,3,5} contains 5 and only {3,4}\{3,4\}{3,4} contains 4, but these two sets share the element 3.

  21. [Polynomial Time Reductions] Exact–Cover: given a set EEE and a set PPP of subsets of EEE , do some sets from PPP contain each element of EEE exactly once? Subset–Sum: given integers SSS and a target TTT , does a subset of SSS add up to TTT ?Why does it not work to map each set in PPP to its number of elements and TTT to ∣E∣|E|∣E∣ ?

    Sets whose sizes add up to ∣E∣|E|∣E∣ can overlap. Example: E={1,2,3}E = \{1, 2, 3\}E={1,2,3} , P={{1},{1,2}}P = \{\{1\}, \{1, 2\}\}P={{1},{1,2}} gives S={1,2}S = \{1, 2\}S={1,2} , T=3T = 3T=3 : 1+2=31 + 2 = 31+2=3 , but {1}\{1\}{1} and {1,2}\{1, 2\}{1,2} both contain 1 and no set contains 3.

  22. [Polynomial Time Reductions] Exact–Cover: given E={1,…,n}E = \{1, \dots, n\}E={1,…,n} and a set PPP of mmm subsets of EEE , do some sets from PPP contain each element of EEE exactly once? Subset–Sum: given integers SSS and a target TTT , does a subset of SSS add up to TTT ?How does Exact–Cover ⩽P\leqslant_P⩽P​ Subset–Sum work?

    Replace each element iii by bi−1b^{i-1}bi−1 with b=m+1b = m + 1b=m+1 , map each set in PPP to the sum of its elements' numbers, and let TTT be the sum for EEE . In base bbb , each set is a 0/1 digit string, and a sum of distinct sets has digit ccc in position iii when ccc sets contain iii . Since c≤m<bc \le m < bc≤m<b , there are no carries, so the sum equals T=11…1bT = 11\ldots1_bT=11…1b​ exactly when each element is covered once.Example (the book uses b=2b = 2b=2 , which works here): E={1,2,3…

  23. [Polynomial Time Reductions] To reduce Exact–Cover ( E={1,…,n}E = \{1, \dots, n\}E={1,…,n} , a set PPP of subsets of EEE ) to Subset–Sum, the book replaces each element iii by 2i−12^{i-1}2i−1 , each set in PPP by the sum of its elements' numbers, and takes T=2n−1T = 2^n - 1T=2n−1 .Why can base 2 give a wrong answer, and what fixes the reduction?

    Several sets containing the same element produce carries. Base ∣P∣+1|P| + 1∣P∣+1 instead of 2 fixes the reduction. Example: E={1,2,3,4}E = \{1,2,3,4\}E={1,2,3,4} , P={{1},{1,3},{1,4}}P = \{\{1\}, \{1,3\}, \{1,4\}\}P={{1},{1,3},{1,4}} gives S={1,5,9}S = \{1, 5, 9\}S={1,5,9} , T=15T = 15T=15 : 1+5+9=151 + 5 + 9 = 151+5+9=15 , yet 1 is covered three times and 2 not at all. In base 4: S={1,17,65}S = \{1, 17, 65\}S={1,17,65} , T=85T = 85T=85 , and no subset of SSS adds up to 85.

  24. [Polynomial Time Reductions] What is the Set–Partition Problem?

    Given a multiset SSS of positive integers: can SSS be split into disjoint S1,S2S_1, S_2S1​,S2​ with S1∪S2=SS_1 \cup S_2 = SS1​∪S2​=S and equal sums? Example: S={2,3,3,5,7}S = \{2, 3, 3, 5, 7\}S={2,3,3,5,7} : S1={2,3,5}S_1 = \{2, 3, 5\}S1​={2,3,5} and S2={3,7}S_2 = \{3, 7\}S2​={3,7} both have sum 10.In a multiset, elements can be repeated.

  25. [Polynomial Time Reductions] Subset–Sum: given positive integers SSS with sum MMM and a target TTT , does a subset of SSS add up to TTT ? Set–Partition: can a multiset be split into two parts with equal sums?How does Subset–Sum ⩽P\leqslant_P⩽P​ Set–Partition handle the cases M<TM < TM<T , M=TM = TM=T , M=2TM = 2TM=2T ?

    M<TM < TM<T No solution. Example: S={1,2}S = \{1, 2\}S={1,2} , T=5T = 5T=5 . M=TM = TM=T SSS itself is a solution. Example: S={1,2}S = \{1, 2\}S={1,2} , T=3T = 3T=3 . M=2TM = 2TM=2T Call Set–Partition on SSS ; either part is a solution. Example: S={1,2,3}S = \{1, 2, 3\}S={1,2,3} , T=3T = 3T=3 : parts {1,2}\{1, 2\}{1,2} and {3}\{3\}{3} .

  26. [Polynomial Time Reductions] Subset–Sum: given positive integers SSS with sum MMM and a target TTT , does a subset of SSS add up to TTT ? Set–Partition: can a multiset be split into two parts with equal sums?How does Subset–Sum ⩽P\leqslant_P⩽P​ Set–Partition work when T<M<2TT < M < 2TT<M<2T ?

    Add n=2T−Mn = 2T - Mn=2T−M to SSS and call Set–Partition; the part not containing nnn is the solution. The new sum is 2T2T2T , so each part has sum TTT .Example: S={1,3,4,7}S = \{1, 3, 4, 7\}S={1,3,4,7} , T=12T = 12T=12 , M=15M = 15M=15 : add 9; parts {1,4,7}\{1, 4, 7\}{1,4,7} and {3,9}\{3, 9\}{3,9} ; solution {1,4,7}\{1, 4, 7\}{1,4,7} .

  27. [Polynomial Time Reductions] Subset–Sum: given positive integers SSS with sum MMM and a target TTT , does a subset of SSS add up to TTT ? Set–Partition: can a multiset be split into two parts with equal sums?How does Subset–Sum ⩽P\leqslant_P⩽P​ Set–Partition work when M>2TM > 2TM>2T ?

    Add n=M−2Tn = M - 2Tn=M−2T to SSS and call Set–Partition; the part containing nnn , with nnn removed, is the solution. The new sum is 2M−2T2M - 2T2M−2T , so each part has sum M−TM - TM−T , and (M−T)−n=T(M - T) - n = T(M−T)−n=T .Example: S={2,5,8,11,13}S = \{2, 5, 8, 11, 13\}S={2,5,8,11,13} , T=18T = 18T=18 , M=39M = 39M=39 : add 3; parts {8,13}\{8, 13\}{8,13} and {2,3,5,11}\{2, 3, 5, 11\}{2,3,5,11} ; solution {2,5,11}\{2, 5, 11\}{2,5,11} .

  28. [NP–Complete Problems] What is a Boolean formula in conjunctive normal form (CNF)?

    Parentheses of variables or negated variables joined by OR, and these parentheses joined by AND. Example: (x1∨x2∨x4∨x5)∧(¬x1∨¬x3)∧(¬x2∨x3∨¬x6)(x_1 \lor x_2 \lor x_4 \lor x_5) \land (\lnot x_1 \lor \lnot x_3) \land (\lnot x_2 \lor x_3 \lor \lnot x_6)(x1​∨x2​∨x4​∨x5​)∧(¬x1​∨¬x3​)∧(¬x2​∨x3​∨¬x6​)

  29. [NP–Complete Problems] What is the SAT Problem?

    Given a formula in conjunctive normal form, can the variables get truth values 0 or 1 that make the formula true? Example: (x1∨¬x2)∧(¬x1)(x_1 \lor \lnot x_2) \land (\lnot x_1)(x1​∨¬x2​)∧(¬x1​) : yes, x1=0x_1 = 0x1​=0 , x2=0x_2 = 0x2​=0 .

  30. [NP–Complete Problems] Is (x1∨x2∨x4∨x5)∧(¬x1∨¬x3)∧(¬x2∨x3∨¬x6)(x_1 \lor x_2 \lor x_4 \lor x_5) \land (\lnot x_1 \lor \lnot x_3) \land (\lnot x_2 \lor x_3 \lor \lnot x_6)(x1​∨x2​∨x4​∨x5​)∧(¬x1​∨¬x3​)∧(¬x2​∨x3​∨¬x6​) satisfiable?

    Yes, e.g. x1=1x_1 = 1x1​=1 , x2=0x_2 = 0x2​=0 , x3=0x_3 = 0x3​=0 (the others arbitrary).

  31. [NP–Complete Problems] Is x1∧(¬x2∨¬x1)∧(x3∨x2)∧(¬x3∨x2)x_1 \land (\lnot x_2 \lor \lnot x_1) \land (x_3 \lor x_2) \land (\lnot x_3 \lor x_2)x1​∧(¬x2​∨¬x1​)∧(x3​∨x2​)∧(¬x3​∨x2​) satisfiable?

    No. x1=1x_1 = 1x1​=1 forces x2=0x_2 = 0x2​=0 , then x3∨x2x_3 \lor x_2x3​∨x2​ forces x3=1x_3 = 1x3​=1 , and then ¬x3∨x2\lnot x_3 \lor x_2¬x3​∨x2​ is false.

  32. [NP–Complete Problems] Why is SAT in NP\mathcal{NP}NP , and why does trying all assignments not show that SAT is in P\mathcal{P}P ?

    A given assignment is checked in O(n)O(n)O(n) operations ( nnn = size of the formula). Trying all assignments takes 2n2^n2n cases for nnn variables, which is not polynomial. Whether SAT is in P\mathcal{P}P is unknown.

  33. [NP–Complete Problems] What is the 3–SAT Problem?

    SAT for formulas in which every parenthesis has exactly three variables (or negated variables). Example: (x1∨¬x2∨x3)∧(¬x1∨¬x3∨x4)(x_1 \lor \lnot x_2 \lor x_3) \land (\lnot x_1 \lor \lnot x_3 \lor x_4)(x1​∨¬x2​∨x3​)∧(¬x1​∨¬x3​∨x4​)

  34. [NP–Complete Problems] SAT ⩽P\leqslant_P⩽P​ 3–SAT: how is each parenthesis of a CNF formula replaced? ( y1,y2,…y_1, y_2, \dotsy1​,y2​,… are new variables.)

    One variable (x1)(x_1)(x1​) becomes four parentheses with all sign combinations of two new variables: Example: (x1∨y1∨y2)∧(x1∨¬y1∨y2)∧(x1∨y1∨¬y2)∧(x1∨¬y1∨¬y2)(x_1 \lor y_1 \lor y_2) \land (x_1 \lor \lnot y_1 \lor y_2) \land (x_1 \lor y_1 \lor \lnot y_2) \land (x_1 \lor \lnot y_1 \lor \lnot y_2)(x1​∨y1​∨y2​)∧(x1​∨¬y1​∨y2​)∧(x1​∨y1​∨¬y2​)∧(x1​∨¬y1​∨¬y2​) Two variables (x1∨¬x2)(x_1 \lor \lnot x_2)(x1​∨¬x2​) becomes two parentheses with one new variable: Example: (x1∨¬x2∨y1)∧(x1∨¬x2∨¬y1)(x_1 \lor \…

  35. [NP–Complete Problems] In SAT ⩽P\leqslant_P⩽P​ 3–SAT, why is (x1∨y1∨y2)∧(x1∨¬y1∨y2)∧(x1∨y1∨¬y2)∧(x1∨¬y1∨¬y2)(x_1 \lor y_1 \lor y_2) \land (x_1 \lor \lnot y_1 \lor y_2) \land (x_1 \lor y_1 \lor \lnot y_2) \land (x_1 \lor \lnot y_1 \lor \lnot y_2)(x1​∨y1​∨y2​)∧(x1​∨¬y1​∨y2​)∧(x1​∨y1​∨¬y2​)∧(x1​∨¬y1​∨¬y2​) satisfiable exactly when x1x_1x1​ is true?

    For every choice of y1,y2y_1, y_2y1​,y2​ , exactly one of the four parentheses has both yyy -parts false, and that parenthesis needs x1=1x_1 = 1x1​=1 . Example: y1=1y_1 = 1y1​=1 , y2=0y_2 = 0y2​=0 makes x1∨¬y1∨y2x_1 \lor \lnot y_1 \lor y_2x1​∨¬y1​∨y2​ equal to x1x_1x1​ .

  36. [NP–Complete Problems] In SAT ⩽P\leqslant_P⩽P​ 3–SAT, a parenthesis (x1∨x2∨⋯∨xn)(x_1 \lor x_2 \lor \dots \lor x_n)(x1​∨x2​∨⋯∨xn​) with n>3n > 3n>3 is replaced by which chain of 3-variable parentheses?

    (x1∨x2∨y1)∧(¬y1∨x3∨y2)∧⋯∧(¬yn−4∨xn−2∨yn−3)∧(¬yn−3∨xn−1∨xn)\boldsymbol{(x_1 \lor x_2 \lor y_1) \land (\lnot y_1 \lor x_3 \lor y_2) \land \dots \land (\lnot y_{n-4} \lor x_{n-2} \lor y_{n-3}) \land (\lnot y_{n-3} \lor x_{n-1} \lor x_n)}(x1​∨x2​∨y1​)∧(¬y1​∨x3​∨y2​)∧⋯∧(¬yn−4​∨xn−2​∨yn−3​)∧(¬yn−3​∨xn−1​∨xn​) n−3n - 3n−3 new variables, n−2n - 2n−2 parentheses. (The book prints ¬yn−2\lnot y_{n-2}¬yn−2​ in the second-to-last parenthesis; the index there is n−4n - 4n−4 .)Example: (a∨¬b∨¬c∨d)(a \lor \lno…

  37. [NP–Complete Problems] SAT ⩽P\leqslant_P⩽P​ 3–SAT replaces (x1∨⋯∨xn)(x_1 \lor \dots \lor x_n)(x1​∨⋯∨xn​) , n>3n > 3n>3 , by (x1∨x2∨y1)∧(¬y1∨x3∨y2)∧⋯∧(¬yn−3∨xn−1∨xn)(x_1 \lor x_2 \lor y_1) \land (\lnot y_1 \lor x_3 \lor y_2) \land \dots \land (\lnot y_{n-3} \lor x_{n-1} \lor x_n)(x1​∨x2​∨y1​)∧(¬y1​∨x3​∨y2​)∧⋯∧(¬yn−3​∨xn−1​∨xn​) .Why is the chain satisfiable exactly when some xix_ixi​ is true?

    Some xix_ixi​ true: set the earlier yyy 's to 1, the later ones to 0. All xix_ixi​ false: the chain forces every yj=1y_j = 1yj​=1 , and the last parenthesis is false. With all xix_ixi​ false: the first parenthesis forces y1=1y_1 = 1y1​=1 , then ¬y1∨x3∨y2\lnot y_1 \lor x_3 \lor y_2¬y1​∨x3​∨y2​ forces y2=1y_2 = 1y2​=1 , …, up to yn−3=1y_{n-3} = 1yn−3​=1 , which makes ¬yn−3∨xn−1∨xn\lnot y_{n-3} \lor x_{n-1} \lor x_n¬yn−3​∨xn−1​∨xn​ false.Example: (a∨b∨y)∧(¬y∨c∨z)∧(¬z∨d∨e)(a \lor b \lor y) \land (\…

  38. [NP–Complete Problems] Why is the reduction SAT ⩽P\leqslant_P⩽P​ 3–SAT polynomial?

    For a formula with nnn variables, each parenthesis is replaced by at most O(n)O(n)O(n) new parentheses with at most O(n)O(n)O(n) new variables.

  39. [NP–Complete Problems] What is a kkk -clique in an undirected graph?

    A set of kkk vertices in which every two vertices are adjacent. Left: a graph containing a 4-clique. Right: a 4-clique.

  40. [NP–Complete Problems] What is the kkk -Clique Problem?

    Given a graph GGG and an integer kkk : does GGG have a kkk -clique? A graph with a kkk -clique also has 222 -, 333 -, …, (k−1)(k-1)(k−1) -cliques.

  41. [NP–Complete Problems] 3–SAT ⩽P\leqslant_P⩽P​ kkk -Clique: which graph is built from a 3–SAT formula with nnn parentheses, and which kkk is used?

    One vertex per variable occurrence ( 3n3n3n vertices); two vertices are joined unless they are in the same parenthesis or are xix_ixi​ and ¬xi\lnot x_i¬xi​ . k=nk = nk=n . An nnn -clique picks one variable occurrence per parenthesis, with no contradictions; setting those to TRUE satisfies the formula. (x1∨x2∨x3)∧(¬x1∨¬x2∨¬x3)∧(x1∨x2∨¬x3)(x_1 \lor x_2 \lor x_3) \land (\lnot x_1 \lor \lnot x_2 \lor \lnot x_3) \land (x_1 \lor x_2 \lor \lnot x_3)(x1​∨x2​∨x3​)∧(¬x1​∨¬x2​∨¬x3​)∧(x1​∨x2​∨¬x3​)

  42. [NP–Complete Problems] In the graph that 3–SAT ⩽P\leqslant_P⩽P​ kkk -Clique builds (one vertex per variable occurrence), why are two vertices of the same parenthesis not joined, and why are xix_ixi​ and ¬xi\lnot x_i¬xi​ not joined?

    The clique must choose exactly one variable per parenthesis, and xix_ixi​ and ¬xi\lnot x_i¬xi​ cannot both be TRUE. All other pairs are joined: choosing x1x_1x1​ as TRUE allows either x2x_2x2​ or ¬x2\lnot x_2¬x2​ in the same clique.

  43. [NP–Complete Problems] 3–SAT ⩽P\leqslant_P⩽P​ kkk -Clique: one vertex per variable occurrence; vertices are joined unless they are in the same parenthesis or are xix_ixi​ and ¬xi\lnot x_i¬xi​ .Graph for (x1∨x2∨x3)∧(¬x1∨¬x2∨¬x3)∧(x1∨x2∨¬x3)(x_1 \lor x_2 \lor x_3) \land (\lnot x_1 \lor \lnot x_2 \lor \lnot x_3) \land (x_1 \lor x_2 \lor \lnot x_3)(x1​∨x2​∨x3​)∧(¬x1​∨¬x2​∨¬x3​)∧(x1​∨x2​∨¬x3​) (left: first parenthesis, top: second, right: third): Give a 3-clique and the satisfying assignment it give…

    e.g. x1x_1x1​ (first), ¬x2\lnot x_2¬x2​ (second), x1x_1x1​ (third), giving x1=1x_1 = 1x1​=1 , x2=0x_2 = 0x2​=0 . Then each parenthesis has a true variable: x1x_1x1​ , ¬x2\lnot x_2¬x2​ , x1x_1x1​ .

  44. [NP–Complete Problems] When is a language AAA NP\mathcal{NP}NP -complete?

    A∈NPA \in \mathcal{NP}A∈NP , and B⩽PAB \leqslant_P AB⩽P​A for every language B∈NPB \in \mathcal{NP}B∈NP .

  45. [NP–Complete Problems] What does the Cook–Levin Theorem say?

    SAT is NP\mathcal{NP}NP -complete. Stephen Cook proved the theorem in 1971 and later received the Turing Award.

  46. [NP–Complete Problems] What is the main idea of the proof of the Cook–Levin Theorem (SAT is NP\mathcal{NP}NP -complete)?

    Write the operations of a polynomial time nondeterministic Turing machine as a Boolean formula that is satisfiable iff the machine accepts. Every problem in NP\mathcal{NP}NP is decided by a nondeterministic Turing machine in polynomial time; the formula describes the steps of an accepting branch.

  47. [NP–Complete Problems] LLL is NP\mathcal{NP}NP -complete. What must be shown to prove that KKK is NP\mathcal{NP}NP -complete?

    K∈NPK \in \mathcal{NP}K∈NP and L⩽PKL \leqslant_P KL⩽P​K . Every B∈NPB \in \mathcal{NP}B∈NP has B⩽PLB \leqslant_P LB⩽P​L , and B⩽PL⩽PKB \leqslant_P L \leqslant_P KB⩽P​L⩽P​K gives B⩽PKB \leqslant_P KB⩽P​K .Example: SAT is NP\mathcal{NP}NP -complete and SAT ⩽P\leqslant_P⩽P​ 3–SAT, so 3–SAT is NP\mathcal{NP}NP -complete; then 3–SAT ⩽P\leqslant_P⩽P​ kkk -Clique gives the same for kkk -Clique.

  48. [NP–Complete Problems] AAA is NP\mathcal{NP}NP -complete and A∈PA \in \mathcal{P}A∈P . What follows?

    P=NP\boldsymbol{\mathcal{P} = \mathcal{NP}}P=NP Every B∈NPB \in \mathcal{NP}B∈NP has B⩽PAB \leqslant_P AB⩽P​A , and A∈PA \in \mathcal{P}A∈P then gives B∈PB \in \mathcal{P}B∈P .Example: a polynomial time algorithm for kkk -Clique would give polynomial time algorithms for all problems in NP\mathcal{NP}NP .

  49. [NP–Complete Problems] What is the 0/1 Integer Programming Problem (decision version)?

    Given linear constraints on variables x1,…,xnx_1, \dots, x_nx1​,…,xn​ that take only the values 0 or 1: is there an assignment that satisfies all constraints? Example: x1+x2≥2x_1 + x_2 \ge 2x1​+x2​≥2 , 4x1−x3≥34x_1 - x_3 \ge 34x1​−x3​≥3 , x1+4x2−3x3≥4x_1 + 4x_2 - 3x_3 \ge 4x1​+4x2​−3x3​≥4 : yes, x1=1x_1 = 1x1​=1 , x2=1x_2 = 1x2​=1 , x3=0x_3 = 0x3​=0 .The optimization version maximizes the right-hand sides.

  50. [NP–Complete Problems] Do x1+x2≥2x_1 + x_2 \ge 2x1​+x2​≥2 , x1+5x2−4x3≥3\ x_1 + 5x_2 - 4x_3 \ge 3 x1​+5x2​−4x3​≥3 , x1−x2+x3≥1\ x_1 - x_2 + x_3 \ge 1 x1​−x2​+x3​≥1 have a solution with x1,x2,x3∈{0,1}x_1, x_2, x_3 \in \{0, 1\}x1​,x2​,x3​∈{0,1} ?

    No. The first constraint forces x1=x2=1x_1 = x_2 = 1x1​=x2​=1 ; the second then gives 6−4x3≥36 - 4x_3 \ge 36−4x3​≥3 , so x3=0x_3 = 0x3​=0 ; and the third becomes 0≥10 \ge 10≥1 .

  51. [NP–Complete Problems] 3–SAT ⩽P\leqslant_P⩽P​ 0/1 Integer Programming: how is a 3–SAT formula turned into constraints?

    Each parenthesis becomes "sum of its parts ≥1\ge 1≥1 ", with xix_ixi​ for xix_ixi​ and 1−xi1 - x_i1−xi​ for ¬xi\lnot x_i¬xi​ . Example: x2∨x4∨¬x5 ⇒ x2+x4+(1−x5)≥1x_2 \lor x_4 \lor \lnot x_5 \;\Rightarrow\; x_2 + x_4 + (1 - x_5) \ge 1x2​∨x4​∨¬x5​⇒x2​+x4​+(1−x5​)≥1 0/1 Integer Programming is in NP\mathcal{NP}NP (a given assignment is checked in polynomial time), so the problem is NP\mathcal{NP}NP -complete.

  52. [NP–Complete Problems] What is an independent set in a graph, and what is the Independent Set Problem?

    A set of vertices no two of which are adjacent. The problem: given GGG and kkk , does GGG have an independent set of kkk vertices? Example: {1,3,5}\{1, 3, 5\}{1,3,5} and {2,4,6}\{2, 4, 6\}{2,4,6} are independent sets of size 3.

  53. [NP–Complete Problems] What is the largest independent set (no two vertices adjacent) in this graph?

    {1,3,5,7}\{1, 3, 5, 7\}{1,3,5,7} , size 4. No independent set of 5 vertices exists. Vertex 7 is adjacent only to 4 and 6.

  54. [NP–Complete Problems] 3–SAT ⩽P\leqslant_P⩽P​ Independent Set: which graph is built from a 3–SAT formula, and which kkk is used?

    For each parenthesis, three vertices joined to each other (a triangle); also join every xix_ixi​ to every ¬xi\lnot x_i¬xi​ . kkk = number of parentheses. A triangle contains at most one vertex of an independent set, so a set of size kkk takes exactly one variable per parenthesis as TRUE, and the xix_ixi​ – ¬xi\lnot x_i¬xi​ edges exclude contradictory choices. (x1∨¬x2∨x3)∧(x1∨x2∨x4)(x_1 \lor \lnot x_2 \lor x_3) \land (x_1 \lor x_2 \lor x_4)(x1​∨¬x2​∨x3​)∧(x1​∨x2​∨x4​)

  55. [NP–Complete Problems] 3–SAT ⩽P\leqslant_P⩽P​ Independent Set: a triangle per parenthesis, and an edge between every xix_ixi​ and every ¬xi\lnot x_i¬xi​ ; kkk = number of parentheses.Graph for (x1∨x2∨x3)∧(x4∨x3∨x1)∧(¬x4∨¬x1∨x3)(x_1 \lor x_2 \lor x_3) \land (x_4 \lor x_3 \lor x_1) \land (\lnot x_4 \lor \lnot x_1 \lor x_3)(x1​∨x2​∨x3​)∧(x4​∨x3​∨x1​)∧(¬x4​∨¬x1​∨x3​) , k=3k = 3k=3 : Give an independent set of size 3 and the assignment it gives.

    e.g. x2x_2x2​ (first triangle), x3x_3x3​ (second), x3x_3x3​ (third), giving x2=1x_2 = 1x2​=1 , x3=1x_3 = 1x3​=1 . None of the three vertices is joined to another, and each parenthesis contains x2x_2x2​ or x3x_3x3​ .

  56. [NP–Complete Problems] What is a vertex cover in a graph, and what is the Vertex Cover Problem?

    A set of vertices such that every edge has at least one end in the set. The problem: given GGG and kkk , is there a vertex cover of kkk vertices? Example: in the path a−b−ca - b - ca−b−c , {b}\{b\}{b} is a vertex cover.

  57. [NP–Complete Problems] What is the smallest size of a vertex cover (every edge has an end in the set) in this graph?

    4, e.g. {2,4,6,7}\{2, 4, 6, 7\}{2,4,6,7} . No vertex cover of 3 vertices exists. {1,3,5,7,8}\{1, 3, 5, 7, 8\}{1,3,5,7,8} is a vertex cover of size 5.

  58. [NP–Complete Problems] GGG is a graph with nnn vertices. How are its independent sets related to its vertex covers?

    SSS is independent iff the other n−∣S∣n - |S|n−∣S∣ vertices form a vertex cover. So GGG has an independent set of size kkk iff GGG has a vertex cover of size n−kn - kn−k .An edge has no end in the complement of SSS exactly when both ends are in SSS . This gives Independent Set ⩽P\leqslant_P⩽P​ Vertex Cover, so Vertex Cover is NP\mathcal{NP}NP -complete. Black: a vertex cover; white: an independent set.

  59. [NP–Complete Problems] Through which reductions does the book show that Vertex Cover, TSP, 0/1 Integer Programming, Set Partition and kkk -Clique are NP\mathcal{NP}NP -complete?

    SAT →\to→ 3–SAT, then from 3–SAT: Ind. Set →\to→ Vertex Cover; Ham. Cycle →\to→ TSP; 0/1 Int. P.; Exact Cover →\to→ Subset Sum →\to→ Set Partition; kkk -Clique. Dashed: 3–SAT ⩽P\leqslant_P⩽P​ Ham. Cycle and 3–SAT ⩽P\leqslant_P⩽P​ Exact Cover are not proved in the book. Other reductions exist too, e.g. kkk -Clique and Independent Set reduce directly to each other.

  60. [NP–Complete Problems] What is an NP\mathcal{NP}NP -intermediate problem, and are such problems known?

    In NP\mathcal{NP}NP , but neither in P\mathcal{P}P nor NP\mathcal{NP}NP -complete. No natural example is known. A 1975 theorem says such problems exist if P≠NP\mathcal{P} \ne \mathcal{NP}P=NP , but the known ones are constructed artificially. The classes inside NP\mathcal{NP}NP , assuming P≠NP\mathcal{P} \ne \mathcal{NP}P=NP ; the dot "?" is an NP\mathcal{NP}NP -intermediate problem.

  61. [NP–Complete Problems] Are there complexity classes beyond NP\mathcal{NP}NP ?

    Yes, e.g. NP⊆EXP⊆NEXP⊆…\mathcal{NP} \subseteq \mathcal{EXP} \subseteq \mathcal{NEXP} \subseteq \dotsNP⊆EXP⊆NEXP⊆…

  62. [Exercises] Show Set–Partition ⩽P\leqslant_P⩽P​ Subset–Sum. (Set–Partition: can a multiset SSS of positive integers be split into two parts with equal sums? Subset–Sum: does a subset of SSS add up to a target TTT ?)

    Compute the sum MMM of SSS . If MMM is odd, there is no partition; otherwise ask Subset–Sum with T=M/2T = M/2T=M/2 . A subset with sum M/2M/2M/2 and its complement form the two parts.Example: S={2,3,3,5,7}S = \{2, 3, 3, 5, 7\}S={2,3,3,5,7} , M=20M = 20M=20 , T=10T = 10T=10 : {3,7}\{3, 7\}{3,7} .

  63. [Exercises] Show Vertex Cover ⩽P\leqslant_P⩽P​ kkk -Clique.

    GGG (with nnn vertices) has a vertex cover of kkk vertices iff the complement graph G‾\overline{G}G has an (n−k)(n - k)(n−k) -clique. G‾\overline{G}G : same vertices, and two vertices are adjacent exactly when they are not adjacent in GGG . The vertices outside a vertex cover are independent in GGG , i.e. pairwise adjacent in G‾\overline{G}G .Example: the path a−b−ca - b - ca−b−c has the vertex cover {b}\{b\}{b} ; G‾\overline{G}G has the single edge acacac , a 2-clique.

  64. [Exercises] Show kkk -Clique ⩽P\leqslant_P⩽P​ Vertex Cover.

    GGG (with nnn vertices) has a kkk -clique iff the complement graph G‾\overline{G}G has a vertex cover of n−kn - kn−k vertices. A kkk -clique of GGG is an independent set of G‾\overline{G}G , and the other n−kn - kn−k vertices cover all edges of G‾\overline{G}G .

  65. [Exercises] 3–SAT ⩽P\leqslant_P⩽P​ Subset–Sum: a formula has mmm parentheses and vvv variables. Which numbers and which target are used?

    Decimal numbers with mmm parenthesis digits and vvv variable digits; one number per xix_ixi​ and per ¬xi\lnot x_i¬xi​ , two dummy numbers per parenthesis, target 33…3 11…133\ldots3\,11\ldots133…311…1 . The number of xix_ixi​ has 1 in each parenthesis digit where xix_ixi​ occurs and 1 in the digit of variable iii ; the same for ¬xi\lnot x_i¬xi​ . The dummies have a single 1 in their parenthesis digit. Digit 1 for each variable forces choosing exactly one of xix_ixi​ , ¬xi\lnot x_i¬xi​ ; digit 3…

  66. [Exercises] Vertex Cover ⩽P\leqslant_P⩽P​ Subset–Sum: a graph has edges 1,…,m1, \dots, m1,…,m ; is there a vertex cover of kkk vertices? Which numbers and which target are used?

    Base 4: each vertex is 1 followed by mmm edge digits (1 for each incident edge); each edge jjj also gives a dummy 4j−14^{j-1}4j−1 ; target is kkk followed by mmm digits 2. Each edge digit reaches 2 only if one or two chosen vertices cover the edge (the dummy adds at most 1). Edge digits stay below 4, so there are no carries, and the leading part counts the chosen vertices: exactly kkk . The book's hint does not mention the dummies, but the target 2 needs them.Example: 5 edges, a vertex incident…

  67. [Exercises] Show that the 0–1 Knapsack Problem is NP\mathcal{NP}NP -complete: nnn items with prices p1,…,pnp_1, \dots, p_np1​,…,pn​ and weights w1,…,wnw_1, \dots, w_nw1​,…,wn​ ; is there a subset with total value ≥P\ge P≥P and total weight ≤W\le W≤W ?

    Reduce Subset–Sum: take pi=wi=sip_i = w_i = s_ipi​=wi​=si​ and P=W=TP = W = TP=W=T . A subset with value ≥T\ge T≥T and weight ≤T\le T≤T has sum exactly TTT . Knapsack is in NP\mathcal{NP}NP : a given subset is checked in polynomial time.Example: S={3,5,9}S = \{3, 5, 9\}S={3,5,9} , T=8T = 8T=8 : items {3,5}\{3, 5\}{3,5} have value 8 and weight 8.

  68. [Exercises] Show that the Bin Packing Problem is NP\mathcal{NP}NP -complete: given items of sizes s1,…,sns_1, \dots, s_ns1​,…,sn​ with 0≤si≤10 \le s_i \le 10≤si​≤1 and NNN bins of size 1, do the items fit in the bins?

    Reduce Set–Partition: divide every number by half the total sum and take N=2N = 2N=2 bins. The scaled items have total size 2, so they fit in two bins exactly when each bin holds exactly 1, i.e. when the original numbers split into two parts with equal sums.Example: {2,3,3,5,7}\{2, 3, 3, 5, 7\}{2,3,3,5,7} , sum 20, divide by 10: {0.2,0.3,0.3,0.5,0.7}\{0.2, 0.3, 0.3, 0.5, 0.7\}{0.2,0.3,0.3,0.5,0.7} ; bins {0.2,0.3,0.5}\{0.2, 0.3, 0.5\}{0.2,0.3,0.5} and {0.3,0.7}\{0.3, 0.7\}{0.3,0.7} .

  69. [Exercises] Show that the Subgraph Isomorphism Problem is NP\mathcal{NP}NP -complete: given graphs G1G_1G1​ and G2G_2G2​ , does G2G_2G2​ have a subgraph isomorphic to G1G_1G1​ ?

    Reduce kkk -Clique: take G1=KkG_1 = K_kG1​=Kk​ (the complete graph on kkk vertices) and G2=GG_2 = GG2​=G . A subgraph of GGG isomorphic to KkK_kKk​ is exactly a kkk -clique.