P versus NP
Theoretical computer science
The question of whether every decision problem whose yes-instances can be verified in polynomial time, given a suitable certificate, can also be decided in polynomial time.
What is usually left out
The asymmetry is deliberate: NP concerns verifying yes-instances from a certificate, and whether no-instances are equally verifiable is the separate open question of NP versus co-NP. "Checked quickly" is shorthand for this certificate condition, not for checking a proposed answer in the everyday sense.
Related terms
In the atlas
- P versus NP problem — Theoretical computer science, open