Terra Incognita
Mathematics

Is P equal to NP?

Distant horizon

Why it matters

It asks whether every problem whose answer is easy to check is also easy to solve. If so, transport could be scheduled optimally, moving people and goods faster and more cheaply, but public-key cryptography would become impossible.

What we know

Posed in 1971: if a problem is easy to check, is it also easy to solve?

What blocks us

Several major families of proof techniques have been proven insufficient.

Current leads

Geometric complexity theory, circuit lower bounds.

Sub-questions

Related questions

Sources

Not yet reviewed by a specialist.

Last checked: 2026-11-18

History of this question

Back to the map →