P, NP and NP-Complete: Three Ideas Behind the Hardest Problems in Computer Science

If anyone finds a fast way to solve a single NP-complete problem, every problem in the class NP becomes fast to solve as well. That one conditional is why NP-completeness sits at the centre of theoretical computer science, and why a plain Stack Overflow question asking what an NP-complete problem is, and why it matters, has drawn answers with hundreds of votes.

The trouble is vocabulary. P, NP, NP-complete and NP-hard sound like rungs on a ladder of difficulty, but they are built from two different questions: how long it takes to find an answer, and how long it takes to check one. One of the four labels does not even promise what its prefix suggests.

Three ideas do the work: fast checking, reduction and hardness. Get those straight and the rest of this corner of computer science, and the workarounds programmers use when they hit it, falls into place.

Checking an answer is not finding it

NP is the set of decision problems, questions with a yes-or-no answer, for which a yes-answer can be verified in polynomial time by a deterministic Turing machine. Polynomial time means a running time of the form O(n^k), where n is the size of the problem and k is a constant. As the top-voted answer on Stack Overflow notes, polynomial time is often simply used as the definition of “fast”.

The name stands for Non-deterministic Polynomial time. A problem in NP can be solved in polynomial time by a non-deterministic Turing machine, an ordinary one extended with a “choice” function that can pick the right branch at each step. The accepted answer boils the practical meaning down to one requirement: a solution has to be testable in polynomial time.

P is the stricter club: decision problems a deterministic Turing machine can solve outright in polynomial time. Solving a problem is at least as good as checking a proposed answer, so everything in P can also be verified in polynomial time. P is therefore a subset of NP. Whether the two sets are in fact the same is the famous P versus NP question.

Reduction: the move that links problems

A problem x is NP-complete if and only if two things hold: x is in NP, and every other problem in NP can be transformed into x in polynomial time. That transformation is a reduction. You rewrite the input of one problem so that the answer to x on the rewritten input is the answer to the original question, and the rewriting itself has to be cheap.

The accepted answer frames the test from the practitioner's side. Start with a problem whose solutions can be tested in polynomial time. If a known NP problem can be solved by feeding a modified version of its input to your problem, then your problem is NP-complete. One reduction from an established NP-complete problem is enough, because that problem already absorbs everything else in NP.

Why one fast algorithm would change everything

Put the definition to work and the consequence is direct. Suppose someone writes a polynomial-time solver for one NP-complete problem x. Take any problem in NP, transform it into x with a polynomial-time reduction, and run the new solver. A cheap step followed by a fast step is still fast, so every NP problem would fall at once. This is what both Stack Overflow answers single out as the reason the topic matters.

Read in the other direction, the same structure is a warning sign. No known method solves any NP-complete problem in polynomial time. When a problem turns out to be NP-complete or NP-hard, the label tells you that it belongs with a family of problems nobody has managed to solve in realistic time, and that a clever exact algorithm would amount to cracking all of them.

NP-hard, and a prefix that misleads

NP-hard problems are those at least as hard as the hardest problems in NP. Every NP-complete problem is NP-hard. The reverse does not hold: not every NP-hard problem is in NP, and some are not decision problems at all, so they do not even have the yes-or-no shape that NP requires.

That makes NP-complete the overlap of two sets: problems that are in NP and are also NP-hard. The top-voted answer is blunt about the naming, calling it confusing and its usage entrenched and unlikely to change.

What practitioners do with an NP-complete problem

Knowing that a problem is NP-complete does not mean giving up on it. As the accepted answer adds in an edit, there are often approximate solutions. Instead of the exact best answer, the algorithm returns one that is provably close to it.

The important word is provably. An approximation usually comes with an approximation bound, written in special notation, that states how far from the true answer the result can be. That turns a vague “good enough” into a guarantee you can design around: you know the worst case before you run it, rather than discovering it in production.

The open question, and what to check before relying on a label

Nobody knows a polynomial-time method for any NP-complete problem, and nobody has settled whether one exists. That is the P versus NP question, the unresolved line between problems we can check fast and problems we can also solve fast. Until it is settled, NP-completeness is strong evidence that a problem is hard in practice, not a proof that it must be.

Two caveats are worth carrying. “Fast” here means polynomial time, a working definition rather than a stopwatch measurement. And the labels are easy to blur: before trusting a claim that a problem is “NP”, check whether the writer means NP-complete, which is in NP, or NP-hard, which may not be.

This article draws on What is an NP-complete in computer science? and answers to it (1, 2), on the Stack Exchange network, licensed under CC BY-SA 4.0.