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.

Haddaad Ma jiro xisaabis oo ku nool midkan, laakiin qaybaha ka mid ah waa la xisaabi karaa. Ku raaxayso mid ka hooseeya, ama ku qor adiga kuu gaar ah.

Ku hay shaqadaada

A xisaab bilaash ah oo ku daray qoraalada waxbarasho kasta, diiwaanka waxa aad dhamaatay, dhibaatooyinka aad xal u tahay meel kaliya, iyo macallinka aad weydiisan kartaa oo ku saabsan bogga. Xisaabta oo keliya waa u furan yahay qof kasta, la diiwaan geliyey ama aan.

Ku soo biir Ku soo gal

Calaamadaha la isticmaalay halkan

Taab calaamad kasta oo loogu talagalay qeexidda buuxda, sawir, iyo waxa xarfaha oo dhan ka mid ah ka dhigan tahay.

Su'aalaha dadku waydiiyaan

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.

In ka badan Frontiers

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