P vs NP Problem
Is every problem whose solution can be quickly verified also quickly solvable?
Overview
The P vs NP problem asks whether every problem whose solution can be verified quickly can also be solved quickly. Formally, it asks whether the complexity classes P and NP are equal.
Why It Matters
If P = NP, many tasks in cryptography, optimization, and verification would change fundamentally. If P ≠ NP, it confirms a deep separation between solving and verifying.
Current Status
Despite major progress in complexity theory, no proof resolves whether P equals NP. Known barriers (such as relativization and natural proofs) explain why many approaches fail, but they do not settle the question.
What a Solution Would Require
A definitive separation (or equality) proof between P and NP, under the standard Turing machine model, accepted by the complexity community.