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.

Sekarang kau Tiada kalkulator yang dapat menyelesaikan ini, tetapi bahagian-bahagian boleh dikira. Cuba salah satu di bawah, atau taipkan sendiri.

Jaga kerja awak sendiri.

Akaun percuma menambah nota pada setiap pengajaran, rekod apa yang anda selesaikan, masalah yang anda selesaikan di satu tempat, dan seorang guru yang anda boleh tanya tentang halaman ini. Matematik itu sendiri terbuka kepada semua orang, sama ada anda log masuk atau tidak.

Daftar Masuk Log masuk

Simbol yang digunakan di sini

Tekan simbol mana-mana untuk definisi penuh, gambar, dan apa makna setiap huruf dalamnya.

Soalan yang orang tanya

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.

Lebih dalam Frontiers

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