P vs NP: The Million-Dollar Question

P vs. NP: The Most Important Unsolved Problem in Computer Science

Open your phone's Sudoku app. Tap a completed puzzle the app instantly tells you whether it is correct. That check takes milliseconds. Now try solving a blank Sudoku from scratch. Depending on your skill, that might take minutes or hours. The same puzzle. The same logic. But checking a solution is trivially easy while finding one is genuinely hard. This asymmetry easy to verify, hard to find is not just a quirk of Sudoku. It appears throughout mathematics, cryptography, logistics, biology, and economics. Formalising this asymmetry is the P vs. NP problem, posed by Stephen Cook in 1971, still unsolved, and carrying a Clay Mathematics Institute prize of one million dollars.

The Complexity Class P

P (Polynomial Time) is the class of decision problems solvable by a deterministic Turing machine in O(nᵏ) time for some fixed constant k, where n is the input size.

Polynomial time is the theoretical definition of "efficiently solvable." Problems in P include:

• Sorting n numbers: O(n log n) merge sort, quicksort.
• Shortest path in a graph: O(V² ) Dijkstra's algorithm, O(E log V) with a heap.
• Matrix multiplication: O(n³) naive, O(n^2.37) Coppersmith Winograd.
• Primality testing: O((log n)^k) AKS algorithm (Agrawal, Kayal, Saxena, 2002) showed primality is in P.
• Linear programming: polynomial via ellipsoid method (Khachiyan, 1979).

The choice of polynomial (rather than, say, O(2ⁿ)) is motivated by the Cobham Edmonds thesis: polynomial time algorithms are robust across reasonable machine models, while exponential time algorithms are practically infeasible for large inputs.

The Complexity Class NP

NP has two equivalent definitions:

Definition 1 Verifier: NP is the class of decision problems for which a proposed solution can be verified in polynomial time by a deterministic TM.

Definition 2 Nondeterministic TM: NP is the class of problems solvable in polynomial time by a nondeterministic Turing machine (one that can "guess" the right answer and verify it).

Both definitions describe exactly the same class of problems. The name NP stands for Nondeterministic Polynomial it does NOT mean "not polynomial" or "necessarily hard."

Examples of NP problems:

• Sudoku: given a filled in 9×9 grid, verify it satisfies all rules in O(n²).
• Travelling Salesman (decision version): given cities, distances, and bound k does a tour of all cities exist with total distance ≤ k? Verify a proposed tour by summing distances.
• 3-SAT: given a Boolean formula in 3-conjunctive normal form, does a satisfying assignment exist? Verify by plugging in the assignment.
• Graph Coloring: can a graph be coloured with k colours so no adjacent vertices share a colour? Verify by checking each edge.
• Subset Sum: given a set of integers and a target sum T, does a subset add up to T? Verify by summing the proposed subset.

co NP

co NP is the class of problems where NO instances can be verified in polynomial time. If the answer to a problem is "no," and you can verify that efficiently, the problem is in co NP.

• Graph non-3-colourability: verify a graph has no valid 3-coloring? Requires checking all 3ⁿ assignments not obviously efficient.
• Tautology: is a Boolean formula true under all assignments? Verifying "no" (by finding a falsifying assignment) is polynomial; verifying "yes" is not obviously so.

NP ∩ co NP contains problems where both YES and NO can be verified efficiently. Primality testing was long suspected to be in NP ∩ co NP (now known to be in P).

P ⊆ NP: One Containment Is Certain

If a problem is in P solvable in polynomial time then it is also in NP: to verify a solution, simply re solve the problem from scratch in polynomial time, ignoring the proposed solution. Therefore P ⊆ NP.

The open question is whether this containment is strict: is P ⊊ NP (are there problems in NP that are not in P)? Or does P = NP (can every efficiently verifiable problem also be efficiently solved)?

The Complexity Hierarchy

Known relationships: P ⊆ NP ∩ co NP ⊆ PSPACE ⊆ EXPTIME. Whether P = NP is open. Whether NP = co NP is also open (widely believed false).

The P = NP Question and Its Consequences

If P = NP (virtually no one believes this, but the proof remains elusive):

• RSA and elliptic curve cryptography would break. Factoring large integers would become polynomial. The entire public key infrastructure of the internet would collapse.
• AES symmetric encryption would not directly break (it relies on different hardness assumptions), but related constructions would be threatened.
• Every NP complete optimisation problem protein folding, drug design, logistics would become efficiently solvable. Enormous economic and scientific benefits.
• Mathematical proofs could be found automatically: the NP problem "does a proof of this theorem of length ≤ k exist?" would become tractable.

If P ≠ NP (the consensus belief):

• Cryptography is safe: integer factorization, discrete logarithm, and other hard problems remain hard.
• NP complete problems require heuristics, approximation algorithms, and exponential exact solvers.
• The gap between verification and discovery is fundamental to the structure of computation.

Why Cryptography Relies on P ≠ NP

RSA encryption (Rivest, Shamir, Adleman, 1978) relies on the hardness of integer factorisation:

• Multiplying two 2048-bit primes p and q: O((log n)²) polynomial, fast.
• Factoring their product back into p and q: best known algorithm (Number Field Sieve) runs in sub exponential but super polynomial time O(exp((log n)^{1/3})).

Integer factorisation is in NP (verify a factor by dividing), but it is not known to be NP complete. If P = NP, factorisation is certainly polynomial. Even without P = NP, a polynomial factoring algorithm would break RSA. The Clay Prize winner who proves P = NP could theoretically decrypt any RSA encrypted communication ever intercepted.

The Status of the Problem

Stephen Cook introduced the notion of NP completeness in his 1971 paper "The Complexity of Theorem Proving Procedures." Richard Karp followed in 1972 by proving 21 classical problems are NP complete. Cook won the ACM Turing Award in 1982. The Clay Mathematics Institute listed P vs. NP as one of the seven Millennium Prize Problems in 2000, each carrying a USD 1,000,000 prize.

As of 2026, P vs. NP remains unsolved. We lack both a polynomial algorithm for any NP complete problem and a proof that no such algorithm can exist. Most complexity theorists believe P ≠ NP, based on decades of failed attempts to find polynomial algorithms for NP complete problems but mathematical belief is not a proof.

Sources: Cook, S. A. (1971). The complexity of theorem proving procedures. Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 151–158. | Sipser, M. (2013). Introduction to the Theory of Computation (3rd ed.). Cengage. | Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press.