P vs NP

P vs NP is the most famous open question in computer science: is checking an answer essentially as easy as finding one? P is the class of problems we can solve quickly — in polynomial time, meaning the running time grows like n, n^2, n^3, and so on. NP is the class of problems whose answers we can verify quickly, even if finding them might be hard. Every problem in P is also in NP (if you can solve it fast, you can certainly check it fast). The question is whether the reverse holds: does P = NP?

Picture the difference with a jigsaw puzzle. Verifying that a completed puzzle is correct is easy — glance at it and you are done. Assembling it from a heap of pieces is much harder. P = NP would mean that, deep down, the assembling is no harder than the checking — that for every problem where we can recognize a good answer quickly, there is also a clever fast way to construct one. Most computer scientists strongly suspect that P ≠ NP, that some problems really are fundamentally harder to solve than to check, but suspicion is not proof.

Be honest about the status: this is unsolved. Nobody has proved P = NP, and nobody has proved P ≠ NP; it is one of the Clay Mathematics Institute's million-dollar Millennium Prize Problems. The stakes are enormous. If P = NP, a vast range of currently intractable problems — including the NP-complete ones, and much of the cryptography that secures modern communication — would suddenly become efficiently solvable. If P ≠ NP, we gain a firm proof that some problems are inherently hard, justifying the daily practice of settling for approximations and heuristics. Either answer would reshape the field; for now, the honest statement is simply that we do not know.