Skip to main content
Mind School·Wonder·Honor-system

P vs NP

Can every problem whose answer is quick to check also be quick to solve?

Play It

▶

Coming Soon

Characterization

P vs NP is the most important open question in computer science and one of the seven Millennium Prize Problems, carrying a $1,000,000 prize from the Clay Mathematics Institute. It asks whether every decision problem whose solution can be verified in polynomial time (the class NP) can also be solved in polynomial time (the class P). The question was formalised independently by Stephen Cook in his 1971 paper "The Complexity of Theorem-Proving Procedures" and by Leonid Levin in 1973. Cook proved that the Boolean satisfiability problem is NP-complete — that every NP problem can be efficiently transformed into it — establishing that if any single NP-complete problem has a polynomial-time solution, they all do. Most computer scientists believe P ≠ NP, but no proof exists. The implications are staggering. If P = NP, then every puzzle whose solution can be quickly checked could be quickly solved: optimal strategies could be computed for nearly any game, cryptographic systems would collapse, and mathematical proof itself would be mechanisable. If P ≠ NP — as almost everyone suspects — then there are intrinsically hard problems: games whose optimal play cannot be computed in any reasonable time, codes that cannot be broken, and searches that cannot be shortcut. The Academy hosts P vs NP in the Mind School because it is the deepest question about the nature of strategic difficulty itself: whether the universe contains problems that are genuinely, irreducibly hard.

Lineage

Stephen Cook, "The Complexity of Theorem-Proving Procedures," Proceedings of the Third Annual ACM Symposium on Theory of Computing, 1971. Leonid Levin, "Universal Sequential Search Problems," Problems of Information Transmission 9(3), 1973. Richard Karp, "Reducibility Among Combinatorial Problems" (1972), identified twenty-one NP-complete problems. The Clay Mathematics Institute designated P vs NP a Millennium Prize Problem in 2000. Scott Aaronson, "P ≟ NP," in Open Problems in Mathematics (Springer, 2016). Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach (Cambridge University Press, 2009).

Quests

Three quests — one for each archetype. Choose the one that fits your way of taking up the discipline.

  • Choose a combinatorial problem of interest to you — a scheduling problem, a puzzle, a game-theoretic question — and construct a polynomial-time reduction from a known NP-complete problem (SAT, 3-SAT, CLIQUE, VERTEX COVER, or another from Karp's list) to your chosen problem, or vice versa. Document the reduction, prove its correctness, and reflect on what the reduction reveals about the structure your problem shares with the NP-complete canon.

    No attestations yetOpen →
    Sign in to claim →

  • Select an NP-complete problem — Boolean satisfiability, graph colouring, the travelling salesman, subset sum, or another of your choosing — and solve a non-trivial instance by hand, without algorithmic assistance. Choose an instance large enough that brute force is uncomfortable but small enough that you can finish. Record the instance, the time spent, the strategy you adopted, and the moment at which the difficulty became palpable.

    No attestations yetOpen →
    Sign in to claim →

  • Explain the P vs NP problem to someone outside computer science. State the question precisely; give one concrete example of a problem in P and one in NP; explain what NP-completeness means and why it matters. Cite Cook's 1971 paper, Karp's 1972 list of twenty-one NP-complete problems, and the Clay Mathematics Institute's Millennium Prize designation. Conclude with a note on what the world would look like if P = NP.

    No attestations yetOpen →
    Sign in to claim →