P, NP and NP-Completeness

1Decision problems, not search problems

P, NP and NP-complete are classes of decision problems: each instance is a yes or a no. 'Is there a tour of cost at most K?' is a decision problem. 'Find the shortest tour' is an optimisation problem. The two are close — if you can find the shortest tour you can answer every K, and if you can answer every K you can binary-search the optimum — but they do not sit in the same class, because NP is a class of languages.

Certificates attach to yes-instances of decision problems. A tour of cost \le K is a certificate for a yes. There is no single certificate convention for 'the shortest tour' that puts the optimisation problem in NP.

Decision questions answer yes or no: on the four-city instance, tour-at-most-17 is no and tour-at-most-18 is yes. The optimisation question answers with the number 18. Those outputs do not share a scale, which is why they sit in different classes.

Split one informal problem

1. Name the objectA tour, a clique, a colouring, a packing.
2. DecisionDoes there exist one with cost / size / colours \le or \ge a given K?
3. OptimisationFind the best such object. NP-hard, typically, but not 'in NP'.

2P, NP, NP-hard, NP-complete

P is the decision problems solvable in time polynomial in the input size — O(n^k) for some constant k. Sorting-related decisions, shortest paths in graphs with nonnegative weights, and 2-colouring sit here.

NP is the decision problems with a polynomial-time verifier: every yes-instance has a short certificate that the verifier accepts, and the verifier rejects every certificate on a no-instance. NP does not mean 'non-polynomial'. Every problem in P is in NP, because the solver itself is a verifier that ignores the certificate.

NP-hard means every problem in NP polynomial-time reduces to it — at least as hard as all of NP. NP-complete means in NP and NP-hard. The NP-complete problems are the hardest problems that are still in NP.

Figure. Schematic containment, not to scale and not a proof that P \neq NP. NP-complete problems sit in the overlap of NP and NP-hard. Halting is NP-hard and outside NP.

Place a problem

1. In P?Is there a poly-time algorithm that always answers yes or no?
2. In NP?Is there a short certificate a poly-time verifier can check on yes-instances?
3. NP-hard?Does every NP problem reduce to it? If also in NP, it is NP-complete.

3Reduction: A ≤p B points at the harder one

A polynomial-time reduction from A to B is a function f, computable in polynomial time, that turns every instance x of A into an instance f(x) of B so that x is a yes if and only if f(x) is a yes. We write A \le_p B. If you can solve B in polynomial time, you can solve A in polynomial time: compute f(x), then run the B-solver.

Hardness travels the other way. If A is already NP-hard and A \le_p B, then B is NP-hard. The usual mistake is to reduce the new problem to the old one and claim a hardness proof.

Figure. The reduction arrow goes from the known-hard problem to the new one. Hardness flows against the arrow: B is at least as hard as A.

To prove B is NP-hard

1. Pick a known-hard ASAT after Cook's theorem; later, any NP-complete problem.
2. Build fA poly-time map from A-instances to B-instances that preserves yes/no.
3. ConcludeA \le_p B, so B is at least as hard as A. If B is also in NP, B is NP-complete.

Using a reduction

def solve_A(x, solve_B, reduce_A_to_B):
    y = reduce_A_to_B(x)   # poly-time f
    return solve_B(y)      # A is yes iff B is yes

4Cook's theorem: SAT is NP-complete

Cook–Levin, the result this syllabus calls Cook's theorem, says that SAT is NP-complete. SAT is the decision problem: given a Boolean formula, does there exist a truth assignment that makes it true? SAT is in NP because a guessed assignment is a certificate the verifier can evaluate in polynomial time.

The hardness half is the content of the proof: every language L in NP has a polynomial-time verifier, and that verifier's computation on an input x and a certificate c can be encoded as a Boolean formula \varphi_{x} that is satisfiable if and only if some certificate makes the verifier accept. The map x \mapsto \varphi_{x} is the reduction L \le_p SAT. You do not need the tableau details to use the theorem: after it, SAT is a legal starting point for every later NP-completeness proof.

Figure. Cook–Levin encodes an arbitrary NP verifier on x and certificate c as a formula φ_x that is satisfiable exactly when some certificate is accepted. SAT is therefore NP-complete and later proofs may reduce from SAT.

What the theorem gives you

1. SAT is in NPA truth assignment is a short certificate; evaluating the formula is poly-time.
2. Every L \in NP reduces to SATEncode the verifier's computation as a formula. That is the proof, not a second definition of NP.
3. AfterwardsTo prove a new B is NPC, show B \in NP and SAT \le_p B (or C \le_p B for any already-NPC C).

5One NPC algorithm in P would collapse P = NP

Suppose some NP-complete problem X had a polynomial-time algorithm. Take any L in NP. By NP-hardness of X we have L \le_p X, so L is solvable in polynomial time too: reduce, then run the X-solver. Therefore NP \subseteq P. Combined with the always-true P \subseteq NP, we get P = NP.

That is why a claimed poly-time algorithm for SAT, for clique, or for TSP-decision is a claim that P = NP. Nobody has one that has survived checking, and nobody has a proof that none exists. The working stance in algorithm design is: treat NPC problems as ones you solve exactly only on small n, or approximately, or by exploiting special structure (bipartite, bounded treewidth, tiny k).

Figure. If an NPC X is in P, every L in NP rides the reduction into X and comes out in P.

The collapse

1. Assume X \in P and X is NPCX has a poly-time solver, and every L \in NP reduces to X.
2. TransferEach L is 'reduce, then solve X' — still poly-time.
3. ConcludeNP \subseteq P, hence P = NP.

6NP-hard need not be in NP

NP-complete is a narrower badge than NP-hard. Completeness requires membership in NP. Hardness does not. The Halting problem is NP-hard — every NP problem reduces to it — and it is undecidable, so it is not in NP. Optimisation TSP is NP-hard and is not a decision language, so it is not NP-complete.

Clique, chromatic-number and TSP-decision — the three syllabus graph problems — are NP-complete and each has a short certificate. Their optimisation twins (largest clique, \chi(G), shortest tour) stay NP-hard and outside the NPC roster.

Figure. Bars are a badge count, not a hardness ranking: 2 means in NP and NP-hard (NPC); 1 means NP-hard only.

Which badge

1. In NP and NP-hardNP-complete — SAT, clique-decision, TSP-decision, 3-colouring.
2. NP-hard, not in NPHalting; optimisation TSP; 'find the largest clique'.
3. In NP, not known hardEvery problem in P; also problems in NP that are not known to be NPC (the P-versus-NP gap).