Lesson 15 of 16

Hard Problems and Approximate Answers

Given a proposed tour, adding its travel distances is easy. Finding the shortest of all possible tours can be much harder. Checking an answer and finding an answer are different tasks.

What P and NP mean

These definitions concern decision problems, whose answers are yes or no.

• P: Problems solvable in polynomial time in the input length.
• NP: Problems whose yes answers have certificates verifiable in polynomial time.
• NP-hard: Every problem in NP can be transformed into this problem in polynomial time. An NP-hard problem need not itself belong to NP.
• NP-complete: Both in NP and NP-hard.

P is contained in NP. Whether they are equal remains unresolved. NP does not mean “unsolvable” or “proven to require exponential time.” See the Clay Mathematics Institute’s P vs NP overview.

Practical choices

Small inputs may permit exact exhaustive search or pruning. Special input structure can also help. For large inputs, consider whether a good answer obtained quickly meets the requirement.

An approximation algorithm gives a mathematical bound on its distance from optimality. A heuristic that works well empirically need not carry such a guarantee.

For example, to cover every edge of an undirected graph with selected vertices, repeatedly choose both endpoints of an uncovered edge and remove their incident edges. The chosen edges share no endpoints, so every optimal cover needs at least one vertex per chosen edge. We select two each, giving at most twice the optimal number.

Randomness is a separate choice

Randomized methods use random choices. A Monte Carlo method may allow an error probability; a Las Vegas method preserves correctness while its running time may vary. Approximation, randomness, and heuristics are not synonyms.

Check your understanding

A minimization algorithm guarantees at most twice the optimum. If the optimum is 10, must it return 20?