What a Resolution of P versus NP Would Actually Look Like

A resolution of the P versus NP problem would not be a clever algorithm for Sudoku or the travelling salesman problem. It would be a mathematical proof, and the two possible outcomes look very different. (For the underlying question and why it matters, see P vs NP Problem: Fundamentals Explained.) ## Proving P ≠ NP (the consensus expectation) To prove P ≠ NP you must show that no algorithm whatsoever — however clever — can solve an NP-complete problem in polynomial time. This requires reasoning about the *entire space of possible algorithms* and demonstrating a fundamental barrier, not merely failing to find a fast one. This is extraordinarily hard precisely because it is a universal negative claim. ## Proving P = NP (the explosive case) A proof that P = NP would most naturally proceed through a polynomial-time reduction: a general method to convert any NP problem into a canonical form such as SAT and solve that. You would not write a separate solver for each problem — NP-completeness guarantees they are interreducible, so one efficient method propagates to all of them. ## Constructive versus non-constructive A **constructive** proof hands you a working algorithm. The SAT reduction is constructive: when a solver returns a satisfying assignment, you decode it directly into the original problem's answer. A **non-constructive** proof is more abstract — it shows that an efficient algorithm *must exist* via a purely existential argument, without ever describing what the algorithm does. You would know a fast solution exists in principle, but the proof itself would not hand you the algorithm or the answer. ## The oracle / relativization barrier P versus NP has been studied with oracles — hypothetical black boxes that answer certain questions for free. Baker, Gill, and Solovay (1975) constructed one oracle relative to which P = NP and another relative to which P ≠ NP. This means any valid proof of P versus NP **cannot rely on oracle-relativizing techniques alone** (such as plain diagonalization), because those techniques behave identically in both oracle worlds. This single result ruled out an entire family of proof strategies — the relativization barrier. ## 'Polynomial' does not mean 'fast' Even a constructive proof of P = NP need not be practically useful. An algorithm running in O(n^10000) is polynomial by definition but uselessly slow for any real input. The classification is about asymptotic growth class, not real-world speed. ## Why one proof covers wildly different problems The reason a single result settles Sudoku, routing, and map-colouring at once is NP-completeness: all NP-complete problems are the same problem in disguise, interreducible in polynomial time. See The Sudoku-to-SAT Reduction: How to Translate One Problem Into Another for a concrete worked reduction.