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.