Skip to content
Tutorials Center
My learning

Topics

Lesson 58 of 59 ยท Practice and Review

Practice: Complexity Problems

Practice problems on P, NP, verifiers, reductions and NP-completeness proofs, with tested Python verifiers, a Hamiltonian path reduction, 2-SAT in P and pseudo-polynomial DP.

Complexity questions come in a few recurring types: show this problem is in NP, classify this problem, prove this problem is NP-complete, and spot the mistake in this reduction. This lesson gives a worked example of each type, together with programs that test the solutions, so you can see the abstract definitions working on concrete instances.

Type 1: show a problem is in NP

The recipe has two parts: say what the certificate is, and describe a polynomial-time verifier. Always bound the certificate's length by a polynomial in the input size.

Problems. Show that each of the following is in NP: CLIQUE (a graph and k), 3-COLORING, VERTEX-COVER (a graph and k), SAT.

Problem Certificate Verifier checks
CLIQUE the k vertices k distinct vertices, every pair joined by an edge (O(kยฒ) lookups)
3-COLORING a color for each vertex each color is one of three, endpoints of every edge differ (O(n + m))
VERTEX-COVER the k vertices k distinct vertices, every edge has an endpoint in the set (O(m))
SAT a truth assignment evaluate every clause (O(formula size))
Python Polynomial-time verifiers for four NP problems

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Verification takes at most a few passes over the input, but the search space grows as 3^n: the heart of NP.

Type 2: classify the problem

Decide whether each problem is known to be in P or NP-complete, and say why. A useful habit is to compare with a nearby problem.

Problem Class Reason
Is a graph bipartite (2-colorable)? P breadth-first search with two colors
Is a graph 3-colorable? NP-complete reduction from 3-SAT
Is there an Euler circuit (every edge once)? P check connectivity and even degrees
Is there a Hamiltonian cycle (every vertex once)? NP-complete classic
Shortest path from s to t P Dijkstra or BFS
Longest simple path from s to t NP-complete contains Hamiltonian path
2-SAT P implication graph and strongly connected components
3-SAT NP-complete Cook-Levin and clause splitting
Minimum spanning tree P Kruskal or Prim
Is a number prime? P the AKS primality test
Integer factorization (decision form) in NP โˆฉ coNP; not known to be in P open
Subset sum with numbers written in binary NP-complete weak NP-completeness

The next program runs two of the easy-looking cases that hide a trap. First, 2-SAT is in P: build an implication graph (each clause (a โˆจ b) gives ยฌa โ†’ b and ยฌb โ†’ a); the formula is unsatisfiable exactly when some variable x and its negation reach each other. Second, subset sum has a dynamic program whose table size depends on the value of the target, which is exponential in the number of bits: pseudo-polynomial time, not polynomial.

Python 2-SAT in polynomial time, and pseudo-polynomial subset sum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each extra bit in the target doubles the work. That is the practical meaning of "pseudo-polynomial": polynomial in the numbers, exponential in their encoding.

Type 3: prove NP-completeness

Problem. Show that HAMILTONIAN-CYCLE (undirected) is NP-complete, assuming HAMILTONIAN-PATH (find a path from s to t visiting every vertex once) is NP-complete.

In NP: the certificate is the cycle; checking it takes polynomial time. NP-hard: reduce HAMPATH to HAMCYCLE. Given (G, s, t), build G' by adding one new vertex z joined to exactly s and t. If G has a Hamiltonian path from s to t, then closing it through z gives a Hamiltonian cycle of G'. Conversely, a Hamiltonian cycle in G' must pass through z, using exactly its two edges, so removing z leaves a Hamiltonian path from s to t in G. The construction adds one vertex and two edges: polynomial.

Python Testing the Hamiltonian path to cycle reduction

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two mistakes commonly ruin reduction proofs. Wrong direction: reducing the new problem to the known one proves nothing about hardness. One-way correctness: showing "yes maps to yes" without "yes comes only from yes". Always write both directions.

Type 4: spot the mistake

  1. "SAT is in NP, so it is solvable in polynomial time." Wrong: NP membership only says solutions are easy to check.
  2. "The best known algorithm for SAT takes exponential time, so SAT is not in P." Wrong: no proof of a lower bound exists; a belief is not a theorem.
  3. "The knapsack DP runs in O(nW), so knapsack is in P." Wrong: W is a number written in binary, so O(nW) is exponential in the input length.
  4. "I reduced 3-SAT to my problem X in exponential time, so X is NP-hard." Wrong: the reduction must be polynomial.
  5. "To prove X is NP-complete I reduced X to 3-SAT." Wrong direction: that only shows X is in NP (if the reduction is polynomial) and no more.

More problems to try

  1. Show INDEPENDENT-SET is NP-complete from CLIQUE using the complement graph (see the reductions lesson).
  2. Show that DOMINATING-SET is in NP and give a verifier.
  3. Show that if P = NP then every language in P except โˆ… and ฮฃ* is NP-complete. (Hint: reductions of this kind may map yes-instances to a fixed yes-instance and no-instances to a fixed no-instance.)
  4. Why is "does this Turing machine halt within n steps on input w, with n written in unary?" in P, and what changes when n is written in binary?
  5. Give an argument that PATH is in NL by describing a nondeterministic logarithmic-space guesser.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What are the two parts of a proof that a language is in NP?

    NP membership means yes-instances have short certificates that a deterministic polynomial-time algorithm can check.
  2. 2. In the Hamiltonian path to cycle reduction, why do we join the new vertex z to s and t only?

    z has degree two, so a cycle through it must use both edges, which forces the rest of the cycle to be an s-to-t Hamiltonian path.
  3. 3. The knapsack dynamic program runs in O(nW). Why is this not a polynomial-time algorithm?

    Input length counts bits. A W with b bits can be about 2^b, so the running time is exponential in the input length.
  4. 4. Which of these problems is in P?

    2-SAT is solved in linear time with strongly connected components; the others are NP-complete.

Summary

  • To place a problem in NP, give a polynomial-length certificate and a polynomial-time verifier.
  • Classify by comparing with a neighbor: bipartite versus 3-colorable, Euler versus Hamiltonian, 2-SAT versus 3-SAT.
  • NP-completeness proofs have two parts (in NP; reduce a known NP-complete problem to it) and the reduction needs both directions and polynomial time.
  • Pseudo-polynomial algorithms are polynomial in the value of the numbers, not in the length of their encoding.
  • Typical errors: wrong reduction direction, confusing "in NP" with "hard", treating belief as proof.

Next: Theory of Computation Review and Cheat Sheet