Every station so far ended with a method that runs in a reasonable time. Some problems seem to have no such method: the best known ones try a share of all possible answers, which grows exponentially. This station is about those problems: how to tell them apart, how to prove a problem belongs to the hard group, and what to do when it does.
Three kinds of question
The same problem can be asked in three ways. For vertex cover (FLOW-5), a set of vertices that touches every edge:
- Decision: is there a cover with at most k vertices? The answer is yes or no.
- Optimisation: how small can a cover be?
- Search: find a smallest cover.
The theory works with decision questions, because yes or no answers are the simplest to compare. Little is lost: with a fast decision method you can find the smallest k by binary search over k (BSRC-4), and the last section shows how to find the cover itself.
P: answered in polynomial time
The size of an input is the length needed to write it down: for a graph, about V + E; for a number N, its digits, about log₂ N bits (the number of times N can be halved). A method runs in polynomial time if its steps are at most c · nᵏ for an input of size n, for some fixed numbers c and k (nᵏ is k copies of n multiplied together). P is the class of decision problems that have a polynomial-time method. Everything in this course up to now is in P: sorting, shortest paths, matching, maximum flow, 2-SAT.
Why polynomials, and not some other limit? Two reasons. A polynomial-time method that calls a polynomial-time method a polynomial number of times is still polynomial, so the class is closed under combining methods. And the class is the same on every reasonable model of a computer. In practice, problems in P usually have methods with small k.
NP: checked in polynomial time
For many problems, a yes answer comes with a short proof that is easy to check. Can a graph be split into three groups with no edge inside a group (GRPH-6)? Finding a split may take a long search, but if someone hands you one, you check each edge once. Step through the figure.
Can these vertices be split into three groups, 0, 1 and 2, so that no edge joins two vertices of one group? Finding such a split may be hard. But someone hands you one (the tags): checking it is easy.
NP is the class of decision problems where every yes answer has a certificate, a proof of polynomial length, and a polynomial-time checker (a verifier) that accepts a correct certificate and rejects every claimed certificate for a no answer.
- SAT (a formula of and, or and not over true/false variables: can it be made true?): the certificate is an assignment; check every clause. 3-SAT is SAT where each clause has three conditions (CONN-4).
- Hamiltonian cycle (a cycle through every vertex once): the certificate is the order of the vertices.
- Subset sum (do some of these numbers add up to exactly t?): the certificate is the chosen numbers.
- Knapsack, vertex cover, travelling salesman as decisions (“value at least v?”, “cover of at most k?”, “tour of at most L?”): the certificate is the packing, the cover or the tour.
Every problem in P is in NP: the checker can ignore the certificate and solve the problem. The name NP means “nondeterministic polynomial”: a machine that could guess the certificate would answer in polynomial time. Note the asymmetry. A yes for SAT has a short proof; a no (“no assignment works”) has no known short proof. Problems whose no answers have short proofs form a class called co-NP.
NP-hard and NP-complete
A reduction from problem A to problem B (lesson 2) is a polynomial-time way to turn any question x about A into a question f(x) about B with the same answer. Then a fast method for B gives a fast method for A: compute f(x) and ask B. We write A ≤ B: A is no harder than B.
- B is NP-hard if every problem in NP reduces to B. A fast method for B would give fast methods for all of NP.
- B is NP-complete if it is NP-hard and also in NP. These are the hardest problems in NP.
Cook–Levin (1971, 1973): SAT is NP-complete. The proof, in outline: take any problem A in NP, with its checker. Running the checker on x and a certificate is a sequence of polynomially many steps, each changing a polynomial amount of memory. Write the whole run as a table, one row per step, one column per memory cell. Each cell of a row is decided by a few cells of the row before, by the checker’s fixed rules, and each such rule can be written as a handful of clauses. Add clauses that fix the input x in the first row and demand “yes” in the last. The certificate’s bits are left free. The formula can be made true exactly when some certificate makes the checker say yes, and it is of polynomial size. So A ≤ SAT.
After that, one reduction is enough for each new problem: if SAT ≤ B and B is in NP, then B is NP-complete, because reductions can be chained. Karp (1972) did this for 21 problems, including 3-SAT, vertex cover, clique, Hamiltonian cycle, three-colouring and subset sum. Thousands are known now.
P against NP
Is P equal to NP? Nobody knows. It is the best known open question in computer science, with a million-dollar prize offered by the Clay Mathematics Institute. If one NP-complete problem had a polynomial method, all would. Most researchers believe P ≠ NP, partly because nobody has found a fast method for any of thousands of these problems, in decades of trying.
For a programmer, “this is NP-hard” is not the end. It means: do not expect a method that is fast and exact on every input. Instead:
- Small inputs: exponential methods that are as small as possible, such as bitmask DP (ADDP-4) or meeting in the middle (BITS-5).
- Special cases: independent sets on trees (ADDP-1), vertex cover in bipartite graphs (FLOW-5), 2-SAT (CONN-4), knapsacks with small weights (DYNP-8).
- Exact but usually fast: branch and bound (lesson 3) and modern SAT and integer programming solvers.
- Close enough, with a proof: approximation algorithms (lesson 4).
Finding an answer with a yes/no helper
Decision questions lose little, as promised. Suppose sat(F) answers whether a formula F can be made true. To find an assignment, first ask about F itself. Then fix the variables one by one: ask whether F stays satisfiable with x₁ = True added; if yes, keep it, and if no, x₁ must be False. Continue with x₂ under the choices so far. The third version of the figure does this.
A clause with a single condition, such as [x], forces that variable: adding it to the formula is how “with x = True” is asked. Each question adds one such clause for every variable fixed so far.
Why it is right. After each step, the formula with the choices so far is still satisfiable: either sat said so, or x = True was impossible while an answer existed, so that answer has x = False. After the last variable every choice is fixed and still satisfiable, so the choices are an answer. That is n + 1 questions. Problems where finding reduces to deciding like this are called self-reducible; all the NP-complete problems of this station are.
Now try HARD-P1, An answer from a yes/no helper.
HARD-1 counts as completed once you step through the figure to the last step.