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.

Now you Ոչ մի հաշվիչ չի կարող լուծել այս խնդիրը, բայց դրա մասերը հաշվարկելի են։ Փորձեք ստորեւ նշվածներից մեկը կամ գրեք ձեր սեփականը։

Ձեր սեփական աշխատանքը շարունակեք

Ազատ հաշիվը յուրաքանչյուր դասավանդման համար գրառումներ է ավելացնում, Ձեր ավարտելիք դասերի և լուծված խնդիրների ցուցակ է պահում մեկ տեղում, և ուսուցիչ, ում կարող եք հարցնել այս էջի մասին։ Մաթեմատիկան բաց է բոլորի համար, անկախ նրանից մուտքագրվել եք արդյոք կամ ոչ։

Գրանցվել Գրանցում

Օգտագործված սիմվոլներ

Տեղադրեք ցանկացած նշան՝ ամբողջական սահմանման, նկարի և դրա մեջ ամեն մի տառի իմաստը տեսնելու համար։

Հարցեր, որոնք մարդիկ տալիս են :

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.

Ցուցադրել Frontiers

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