What is P versus NP?

P versus NP is the biggest open question in computer science. It asks whether finding an answer is fundamentally harder than checking one.

The two classes

P is the set of problems a computer can solve quickly, meaning in time that grows at a manageable, polynomial rate as the problem gets bigger. Sorting a list is in P.

NP is the set of problems where a proposed answer can be checked quickly, even if finding it seems to take forever. A Sudoku is a good picture: solving a hard one takes effort, but checking a finished grid takes seconds.

Every problem in P is also in NP, since if you can solve something quickly you can check it quickly. The question is whether the reverse holds. Is every quickly checkable problem also quickly solvable? Most experts suspect the answer is no, but nobody has proved it either way. The Clay Mathematics Institute lists it among its Millennium Prize Problems, with a million dollar prize for a solution.

Why it matters

Thousands of practical problems sit in the hardest part of NP, called NP-complete. These include scheduling, packing, routing and the logic puzzle 3-SAT. If someone found a fast method for one of them, the same method would solve all of them. That is why a single breakthrough would reshape fields from logistics to chip design.

Much of modern encryption also leans on the assumption that certain problems are hard to solve but easy to check. A fast method for every NP problem would threaten that assumption, though encryption relies on specific problems, so the consequences would depend on the details of the method.

What it means for AI

Today's AI models do not solve NP-complete problems by magic. They find good approximate answers, and they can write or call specialized solvers. When a lab claims an AI found something new in this area, the right questions are whether the proof is machine-checked, for example in Lean, and whether independent experts have reviewed it.

Neighboring ideas

A stronger conjecture, the Exponential Time Hypothesis, says 3-SAT needs exponential time, not just more than polynomial time. Proving statements like these is a form of formal verification when done with software checking every step.

Common questions

Does P equal NP? Unknown, and most researchers believe not. Would proving it break the internet? Not automatically. It would depend on whether the proof gave a practical method. Has AI solved it? Not as far as anyone has shown.