The P and NP Classes

Since 2000, the Clay Mathematics Institute has offered 1 million dollars for answering whether P equals NP. Nobody has collected. But the real stakes are higher: if P = NP, all cryptography collapses within hours. RSA, TLS, Bitcoin - gone. The gap between $O(n^2)$ and $O(2^n)$ at $n = 100$: 10,000 operations versus $10^{30}$ - more than atoms in the Earth. Bitcoin mining is intentionally an NP problem. Not a bug. A feature.

• **Cryptography** - RSA and Diffie-Hellman rely on the assumption that factorization and discrete logarithm are not in P; if P = NP, it all falls apart
• **Bitcoin and proof-of-work** - mining is deliberately built on an NP problem: finding a hash is hard, verifying it is instant
• **SAT solvers** - chip verification at Intel, FPGA synthesis, compiler schedulers - all solved through approximate NP methods
• **Logistics** - FedEx and UPS routing, Amazon warehouse bin packing - NP-hard problems tackled with heuristics

The Class P

Since 2000, the Clay Mathematics Institute has offered 1 million dollars for solving the P vs NP question. Nobody has collected. The gap between $O(n^2)$ and $O(2^n)$ at $n = 100$: 10,000 operations versus $10^{30}$ - more than the atoms in the Earth. Class **P** is the line separating problems a computer can solve in a lifetime from those that would take ages. And that line is what protects every bank account on the planet.

**P** is the class of decision problems (yes/no answer) solvable by a deterministic Turing machine in polynomial time $O(n^k)$, where $n$ is the input size and $k$ is a constant independent of $n$.

Why polynomial time specifically? Because polynomials are **closed under composition**: a polynomial of a polynomial is again a polynomial. If each step of an algorithm is polynomial and the number of steps is polynomial, the total running time is polynomial. This makes P a robust, well-behaved class.

The gap between $O(n^2)$ and $O(2^n)$ is vast. For $n = 100$: $n^2 = 10{,}000$ operations (instant), while $2^n \approx 10^{30}$ (more than atoms in the Earth). Bitcoin mining is intentionally built on a problem outside P - that's not a bug, it's a design decision. The boundary of class P is the boundary of practical computability.

The Class NP and Nondeterminism

What if a computer could **guess**? Consider a machine that at each step forks and explores all possibilities in parallel. If even one branch finds a solution, the problem is solved. This is the **nondeterministic Turing machine (NTM)**. The class of problems it solves in polynomial time is **NP**. Finding a 9x9 Sudoku is hard; verifying one takes microseconds. Computing the optimal UPS route is hard; checking its length takes a second. That asymmetry is what NP captures.

**NP** (Nondeterministic Polynomial) is the class of problems solvable by a nondeterministic Turing machine in polynomial time. Equivalent definition: NP is the class of problems for which a **proposed solution can be verified** in polynomial time.

**N in NP stands for Nondeterministic, not "Non-Polynomial"!** This is critical. P ⊆ NP - every problem in P is also in NP (a deterministic machine is a special case of a nondeterministic one). SAT solvers used to verify Intel chips, graph coloring in register allocation, FedEx routing - all NP problems solved approximately, because no exact polynomial algorithm has ever been found.

Examples of NP problems: the Traveling Salesman Problem (TSP), graph coloring, the knapsack problem, SAT. For each of them a proposed solution can be **verified** quickly, but **finding** one quickly is unknown.

Solution Verification

The nondeterministic machine is an abstraction. In practice, a more useful definition of NP is: a problem is in NP if for every "yes" instance there exists a **proof** (certificate) that can be **verified** in polynomial time. Not finding a solution - but verifying a proposed one. This is why NP problems are not useless: their solutions can be efficiently validated.

Alternative definition of NP: a problem L ∈ NP if there exists a polynomial-time **verifier** V(x, c) such that: for every "yes" instance x there is a certificate c of polynomial length with V(x, c) = true. The verifier runs in polynomial time in |x|.

NP has an asymmetry: for a "yes" answer there is a short proof (certificate). But for a "no" answer - not necessarily! The class of problems where the "no" answer also has a short proof is called **coNP**. Whether NP = coNP is also open.

The Certificate

A certificate (witness) is a "hint" that proves the answer is "yes". The certificate's size must be polynomial in the input size. For SAT - a truth assignment. For CLIQUE - the list of vertices. For Hamiltonian Cycle - the cycle itself. For a mathematical theorem - the step-by-step proof. The gap between "checking a proof" and "finding a proof" is exactly the heart of P vs NP.

Formally: for a problem L ∈ NP there exists a polynomial-time verifier V and a polynomial p such that x ∈ L ⟺ ∃c: |c| ≤ p(|x|) and V(x, c) accepts. The certificate c has length at most p(|x|) - polynomial in the input.

Critically: the certificate must be of **polynomial size**. Allowing exponential certificates would make the NP definition trivial (the entire brute-force search tree could be encoded in the certificate). The length bound is the key to a meaningful definition.

To summarize: P contains problems we can solve quickly. NP contains problems whose solutions can be verified quickly (given a certificate). The P = NP question asks: is every problem that is easy to verify also easy to solve? Intuition says no - verifying a proof is easier than discovering one. Bitcoin is worth a trillion dollars precisely because smart people made the right bet that P ≠ NP.

Key Takeaways

• **P** - problems solvable in polynomial time $O(n^k)$; the boundary of practical computability
• **NP** - problems whose solutions are verifiable in polynomial time (Nondeterministic Polynomial, not Non-Polynomial)
• **P ⊆ NP** - every problem in P is also in NP; the question is whether the reverse holds
• **Certificate** - a polynomial-size proof of a "yes" answer, verifiable in polynomial time
• NP problems are not just theory - they are why Bitcoin is worth a trillion dollars and RSA protects the internet

Related Topics

The P and NP classes are the foundation of computational complexity theory:

• NP-Completeness — The hardest problems inside NP - if one is in P, then all are in P
• Classic NP-Complete Problems — 3-SAT, clique, Hamiltonian cycle - concrete examples of NP-complete problems

Вопросы для размышления

• Why do most researchers believe P ≠ NP? What are the arguments for and against?
• If P = NP were true, what would be the practical consequences for cryptography, AI, and mathematics?
• The PRIMES problem (primality testing) was long known to be in NP but not proven to be in P. In 2002 the AKS algorithm showed PRIMES ∈ P. What other problems might move from NP into P?

Связанные уроки

• alg-01-big-o — Without Big-O notation you cannot reason about P and NP classes
• comp-01 — Complexity theory assumes computability: we study complexity only for decidable problems
• ds-01-arrays — Data structures determine concrete algorithm complexity: tree vs array changes O(n) to O(log n)
• dm-01 — NP-complete problems are formulated using combinatorial objects from discrete math: graphs, sets, matrices
• alg-34-approximation