In 1971, Stephen Cook of the University of Toronto published The Complexity of Theorem-Proving Procedures, defining a class — NP-complete — proven in a precise sense to be all equally hard. Richard Karp of Berkeley followed in 1972 with twenty-one such problems — graph colouring, travelling salesman, satisfiability, knapsack — all reducible to one another, and the P vs NP question that emerged (can every problem whose answer can be quickly verified also be quickly solved?) became the biggest open question in computer science. The Clay Mathematics Institute placed it on its 2000 list of seven Millennium Prize Problems with a million-dollar bounty, unclaimed since. Most researchers believe P ≠ NP; no one has proved it.
P is the class of problems solvable in polynomial time (sorting, shortest-path, linear programming sit comfortably inside); NP is the class whose proposed solutions can be verified in polynomial time — Sudoku is the household example, where finding a solution is hard but checking one is trivial. NP-complete problems are the hardest in NP: any NP problem reduces to any NP-complete problem in polynomial time, so a fast algorithm for one would give fast algorithms for all. Cook's 1971 result was that Boolean satisfiability is NP-complete; Karp extended the proof to dozens of natural problems the next year. If P = NP, every NP-complete problem is in P and the consequences are vast — cryptography breaks, optimization (logistics, scheduling, drug design) becomes tractable, AI systems based on search become enormously more powerful. If P ≠ NP, the apparent reality, there is a fundamental gap between checking and finding. The reasons most researchers believe P ≠ NP converge from three directions: decades of intensive failure to find polynomial algorithms for SAT or TSP; formal results showing current proof techniques (relativization, natural proofs, algebrization — Razborov-Rudich, Aaronson-Wigderson) cannot settle the question; and the practical observation that modern cryptography rests on certain problems being hard. Several outcomes remain possible: a small-constant P = NP would be a practical revolution; a galactic algorithm (Lipton's term) in polynomial time with astronomical constants would be theoretically interesting but practically irrelevant; and a few researchers (Aaronson) take seriously the Gödel-style possibility that the question is independent of standard mathematics.
P vs NP is the unspoken hinge of modern technology: the encryption on every banking transaction, HTTPS connection, and secure messaging app rests on believed-hard problems (factoring, discrete log, lattice problems) being actually hard, and the optimization problems faced by logistics firms, airlines, chip designers, and drug companies are NP-hard in practice — handled with heuristics (simulated annealing, genetic algorithms, branch-and-bound, increasingly learned RL heuristics) that work well enough without provable polynomial guarantees. A sufficiently large quantum computer would not solve all NP problems efficiently (the class BQP is not believed to contain NP), but it would break specific cryptographic problems via Shor's algorithm, which is why post-quantum cryptography (lattice-based, hash-based) is now a major deployment programme.