Theory of NP-Completeness

A decision problem has only two answers: YES or NO. Example: "Does this graph have a cycle that visits every vertex exactly once?" — the answer is yes or no.

Many real problems are optimization problems ("find the shortest route"). We can always rephrase them as decision problems ("is there a route shorter than 100 km?"). Studying the decision version keeps the theory simple.

There is a big difference between solving a problem and verifying an answer:

• Solving: find the answer from scratch.
• Verifying: someone hands you a proposed answer (called a certificate or witness) and you just check whether it is correct.

Think of a filled-in Sudoku grid. Solving an empty Sudoku is hard. But checking a completed grid — every row, column, and box has 1–9 once — is fast and easy. The completed grid is the certificate.

P is the set of decision problems that a computer can solve in polynomial time — that is, in time like n, n², or n³ for input size n. These problems are considered "efficiently solvable".

Examples in P:

• Sorting a list — O(n log n).
• Searching for a value — O(n) or O(log n).
• Shortest path in a graph (Dijkstra) — polynomial.

If a problem is in P, we have a fast recipe that always gives the right yes/no answer.

NP stands for Nondeterministic Polynomial time. A problem is in NP if, whenever the answer is YES, there is a certificate that lets us verify the YES answer in polynomial time.

In short: NP problems may be hard to solve, but a correct answer is easy to check.

Examples in NP:

• SAT — is there an assignment of true/false that makes a boolean formula true? (Given the assignment, just plug it in and check.)
• Subset Sum — is there a subset of numbers that adds up to a target? (Given the subset, just add it up.)
• Hamiltonian Cycle — is there a tour visiting every vertex once? (Given the tour, just walk it and check.)

Every problem in P is also in NP: if you can solve it quickly, you can certainly verify it quickly (ignore the certificate and just solve it). So P ⊆ NP.

A reduction is a way to transform one problem into another. We write A ≤p B ("A reduces to B in polynomial time") to mean:

If we had a fast algorithm for B, we could use it to solve A fast too.

The idea: take any input of A, transform it (in polynomial time) into an input of B, solve B, and translate the answer back. So B is "at least as hard as" A.

Tiny concrete example (in words): Suppose you can solve Hamiltonian Cycle (visit every city once and return home). Then you can solve the decision version of the Traveling Salesman Problem on the same cities: give every existing road length 1 and every missing road a huge length, then ask TSP for a tour of total length equal to the number of cities. Such a tour exists only if a Hamiltonian cycle exists. We turned one problem into the other, so Hamiltonian Cycle ≤p TSP.

NP-Hard: a problem is NP-Hard if every problem in NP reduces to it (A ≤p H for all A in NP). It is at least as hard as everything in NP. An NP-Hard problem does not have to be in NP — it may not even be a decision problem, and it may be undecidable (like the Halting Problem).

NP-Complete: a problem is NP-Complete if it is both in NP and NP-Hard. In other words:

NP-Complete = NP ∩ NP-Hard — the hardest problems that still live inside NP.

If you solve any one NP-Complete problem quickly, you can solve them all quickly.

Cook–Levin Theorem: SAT was the first problem proven NP-Complete. This gave us a starting point.

How we prove a new problem X is NP-Complete:

1. Show X is in NP (a certificate is checkable in polynomial time).
2. Pick a known NP-Complete problem K and show K ≤p X.

Since every NP problem already reduces to K, and K reduces to X, every NP problem reduces to X — so X is NP-Hard too, hence NP-Complete. This is how 3-SAT, Clique, Vertex Cover, and Hamiltonian Cycle were all proven NP-Complete.

Here is the famous picture (assuming P ≠ NP). Step through it to see how the regions fit together: P sits inside NP, NP-Hard sits to the side, and NP-Complete is exactly the overlap between NP and NP-Hard.

The biggest open question in computer science is: does P = NP? That is, can every quickly-verifiable problem also be quickly solved?

Most researchers believe P ≠ NP (the diagram above assumes this). But nobody has proved it.

Why you should care:

• If your problem is NP-Complete, do not waste time hunting for a guaranteed-fast exact algorithm — none is known to exist. Instead use approximation algorithms, heuristics, or exact methods that are only fast on small or special inputs.
• If P = NP were ever proved true (with a practical algorithm), it would break modern cryptography, instantly solve scheduling, protein folding, and countless optimization problems.
• Recognizing NP-Completeness early saves you from chasing an impossible-looking goal.

These classes are about verifying, not solving. Below is a verifier for Hamiltonian Cycle: it takes a graph and a proposed cycle (the certificate) and checks it in polynomial time. The existence of such a verifier is exactly what "in NP" means.

There is no single running time here, because P, NP, NP-Hard, and NP-Complete are classes of problems, not one algorithm. The key facts: a certificate can be verified in polynomial time, but for NP-Complete problems no polynomial-time algorithm is known to solve them — and whether one exists (P = NP) is the famous open question.