Symptom

You are handed a scheduling problem. Two hundred tasks, precedence constraints, shared resources, and a deadline. Somebody wants an optimal schedule.

Checking a proposed schedule takes seconds: walk the list, verify each constraint, add up the makespan. Finding one is different. Your search runs for a day and finds nothing. You try simulated annealing, then a genetic algorithm, then branch and bound. Each gives good schedules and none gives the best one, and you cannot tell whether the problem is hard or you are not clever enough.

That gap — between the ease of checking and the difficulty of finding — is the most important open question in computer science, and it is not a curiosity about theoretical machines. It is the shape of your week. The practical question underneath is: when should you stop looking for an exact algorithm? The answer depends on a conjecture nobody has proved, and the professional skill is knowing how to act while it stays unproved.

Statement

P is the class of decision problems solvable by a deterministic Turing machine in time polynomial in the input size.

NP is the class of decision problems whose yes instances have a polynomial-size certificate verifiable in polynomial time. Equivalently, those solvable in polynomial time by a nondeterministic machine.

The question: does P = NP?

$\text{P} \subseteq \text{NP}$ is immediate — if you can solve it you can verify it by ignoring the certificate and re-solving. The question is whether the containment is strict. Nobody knows, and the Clay Institute will pay a million dollars for either answer.

Note the framing that makes it feel less abstract: P is “solvable,” NP is “recognizable-when-shown.” Sudoku, factoring, protein folding, circuit design, theorem proving, and your scheduling problem are all NP: a solution is easy to check. The conjecture $\text{P} \ne \text{NP}$ says that for some of them, finding is genuinely harder than checking — that there is no shortcut past search.

An NP-complete problem is one in NP to which every NP problem reduces in polynomial time (T017). These are the hardest problems in NP, and there are thousands. A polynomial algorithm for any single one collapses the whole class.

Argument

There is no proof to present, so what follows is the case for the conjecture and the reasons it has resisted.

Why almost everyone believes $\text{P} \ne \text{NP}$. Not proof, but the evidence is substantial. Fifty years of intense effort on thousands of NP-complete problems has produced no polynomial algorithm for any of them, and these are problems with enormous commercial value. The asymmetry between verifying and searching feels fundamental: appreciating a proof is not the same skill as finding one, and if P = NP then it is, in a precise sense. Aaronson’s formulation is that P = NP would mean “anyone who could appreciate a symphony could write one,” and the world does not appear to work that way.

A 2019 poll of complexity theorists found 88% believing P ≠ NP. That is not evidence about mathematics but it is evidence about where informed effort is being spent.

Why it is hard: the barriers (T030). Three proof techniques have been ruled out, which is unusual and is the real reason progress stalled.

Relativization (Baker–Gill–Solovay, 1975). There are oracles $A$ and $B$ with $\text{P}^A = \text{NP}^A$ and $\text{P}^B \ne \text{NP}^B$. Any proof that works by simulation — as the halting proof and the time hierarchy theorem do — would relativize, so it would have to hold for both oracles. It cannot. Every technique inherited from computability theory is dead.

Natural proofs (Razborov–Rudich, 1994). Circuit lower bound techniques that are “constructive” and “large” — applying to most functions and checkable efficiently — would break pseudorandom generators. If strong one-way functions exist, which is roughly what we believe, then no natural proof separates P from NP. Most circuit-complexity methods are natural.

Algebrization (Aaronson–Wigderson, 2008). The algebraic techniques that resolved IP = PSPACE relativize in an extended algebraic sense too, and are therefore also insufficient.

So the field knows three large families of techniques that cannot work, and does not know what the fourth family looks like. This is a much more specific situation than “the problem is hard.”

What a proof of P = NP would change. If constructive with a small exponent, essentially everything. Public-key cryptography dies, since breaking RSA and finding discrete logs are in NP. Optimal scheduling, routing, circuit layout, protein structure prediction, and drug design become tractable. Mathematics changes character: finding a proof of length $n$ becomes a polynomial search, so theorem proving is automated up to the length bound. This is why the result would be transformative rather than merely important, and also why it is implausible.

If non-constructive, or constructive with an exponent of 100, nothing changes practically and the world learns something profound.

What a proof of P ≠ NP would change. Directly, less than people expect. We would have proved what we already assume. But the techniques needed would almost certainly be worth more than the theorem — the same way Wiles’s proof of Fermat mattered mostly for the modularity machinery — and cryptography would gain a necessary condition it currently lacks. Note that P ≠ NP does not by itself give secure cryptography: crypto needs average-case hardness, and P ≠ NP is a worst-case statement.

Forbids

Strictly, an open problem forbids nothing. What the surrounding theory forbids is worth stating, because it is what you actually use:

A polynomial algorithm for one NP-complete problem without collapsing all of them. By reduction closure, one is all. So a claimed polynomial SAT algorithm is a claim of P = NP, and should meet that bar of scrutiny.

Proving P ≠ NP by any relativizing, natural, or algebrizing argument. If your proof strategy simulates machines, or produces an efficiently checkable property of hard functions, it is already known to fail. This has saved enormous amounts of wasted effort and is the practical value of the barrier results.

Escaping NP-hardness by restricting to a subclass the reduction still reaches. If 3-SAT reduces to your problem using only instances your restriction permits, you have not escaped.

Does not forbid

It does not say NP-hard problems are unsolvable in practice, and treating it that way is the expensive mistake. SAT solvers dispatch industrial instances with millions of variables daily; Z3 and CVC5 are load-bearing in verification, symbolic execution, and dependency resolution. CPLEX and Gurobi solve integer programs with hundreds of thousands of variables. Real instances have structure — low treewidth, backbone variables, community structure — that worst-case theory does not see. “It’s NP-complete” is a reason to reach for a solver, never a reason to stop.

It does not preclude good approximations. Many NP-hard optimization problems have polynomial approximation schemes. Metric TSP has a 1.5-approximation (Christofides) and, since 2020, slightly better; knapsack has an FPTAS; vertex cover has a trivial 2-approximation. Whether a good approximation exists is a separate question answered by the PCP theorem (T031), and the answers vary by problem: max-cut is approximable to 0.878, and max-clique is not approximable to within $n^{1-\varepsilon}$.

It does not mean NP-complete problems are the hardest problems. PSPACE, EXPTIME, and the undecidable sit above. Generalized chess is EXPTIME-complete; halting is not in NP at all. NP-complete is the bottom of the hard problems, not the top, and treating “NP-hard” as a synonym for “impossible” mislabels the difficulty.

It does not settle whether NP-intermediate problems exist. Ladner’s theorem says that if P ≠ NP then there are problems in NP that are neither in P nor NP-complete. Factoring and graph isomorphism are the natural candidates. Babai’s quasipolynomial algorithm for graph isomorphism moved it much closer to P without landing there, and factoring being easy on a quantum computer while apparently not NP-complete is exactly the kind of structure this space allows.

It does not mean quantum computers solve NP-complete problems. BQP is not believed to contain NP. Grover gives a quadratic speedup on unstructured search — $2^{n/2}$ instead of $2^n$, meaningful but not a collapse — and Shor’s algorithm attacks factoring, which is likely NP-intermediate. The popular claim that quantum computers “try all possibilities at once” is wrong and this is where it does most damage.

Boundary

  • The parameterized view (T033). Rather than asking whether a problem is polynomial in $n$, ask whether it is polynomial in $n$ for fixed parameter $k$. Vertex Cover is $O(2^k n)$: hard in general, easy when the cover is small. This often matches reality better than the P/NP dichotomy.
  • Average case vs. worst case. NP-hardness is a worst-case claim. Cryptography needs problems hard on average with a known distribution, which is a strictly stronger requirement, and it is why lattice problems with worst-case-to-average-case reductions are the post-quantum favourites.
  • The exponential-time hypothesis. Stronger than P ≠ NP: that 3-SAT needs $2^{\Omega(n)}$. ETH and SETH give conditional lower bounds on problems already in P, such as edit distance having no truly subquadratic algorithm. This fine-grained programme is where the field’s practical energy has moved.
  • What counts as a proof attempt. Gerhard Woeginger maintained a list of over a hundred claimed proofs, all wrong. The barriers explain why: a correct proof must use a technique nobody has, so any argument that feels familiar is almost certainly one of the three ruled-out families.
  • Cook–Levin is the next post. All of this rests on there being a first NP-complete problem to reduce from, and T027 is where SAT gets that role.