P versus NP

If a solution can be checked quickly, can it always be found quickly?

The statement. P is the set of problems a computer can solve in time polynomial in the input size; NP is the set whose proposed solutions can be checked in polynomial time. Is P = NP?

In plain words. Checking a completed Sudoku is easy; solving one from scratch seems hard. Checking that a number factors as p × q is easy; finding p and q is the hardness cryptography relies on. P = NP would mean every such “easy to check” problem is secretly easy to solve. Almost everyone believes P ≠ NP; nobody can prove it.

What you need first. Stage 9 (logic, truth tables, counting — the satisfiability problem is a truth-table question), Stage 10 (factoring, why it is slow), Stage 1–2 for reading growth rates like n², 2ⁿ.

The parts. (1) What counts as fast: polynomial vs exponential time, and why the distinction survives changing computers. (2) NP-completeness (Cook–Levin, 1971): thousands of problems — satisfiability, travelling salesman, graph colouring — are each as hard as all of NP, so solving any one fast solves them all. (3) Why the obvious approaches fail: diagonalisation and circuit lower bounds each hit a proven barrier. (4) What a proof would need: a genuinely new way to show that no algorithm can exist.

What is known. Exponential lower bounds exist only for restricted models of computation; the three known barriers (relativisation, natural proofs, algebrisation) explain why current techniques cannot work. A Millennium Prize problem.

Symbols used here

\blacksquare\ \text{or}\ \square

end of proof (halmos)
Marks the point where the statement has been established.

\varphi(n),\ \pi(x)

Euler's totient, prime-counting function
Count of 1..n coprime to n; number of primes up to x.

\zeta(s)

Riemann zeta function
Σ 1/nˢ, continued to the complex plane; its zeros are the Riemann Hypothesis.

O(n^2),\ \Theta,\ \Omega

big-O notation
Grows no faster than n² (up to a constant), for large n.

\frac{\partial u}{\partial t},\ \nabla^2 u

partial derivative in time, Laplacian
Rate of change in time; sum of second partials (the diffusion operator).

Questions people ask

Can I actually work on these?

You can understand them, which is the honest first step and what these pages are for. Working on them means the full path through the stages above and then the research literature — but every person who has made progress started by reading the statement.

Why are they unsolved if so many people have tried?

Usually because the existing tools provably cannot work (the barriers in P vs NP), or because the problem mixes two structures mathematics handles separately (additive and multiplicative in Goldbach and Collatz). A solution needs a genuinely new idea.

Kendini dene.

Daha fazlası Frontiers

The Riemann Hypothesis Navier–Stokes existence and smoothness Goldbach's conjecture The Collatz conjecture The twin prime conjecture