P versus NP Problem

The P versus NP problem asks whether every computational problem whose solution can be quickly verified once found (the class NP) can also be quickly solved from scratch (the class P), or whether some such problems are fundamentally harder to solve than to check. The problem was framed in essentially its modern form in the early 1970s, building on the foundational 1971 work of computer scientist Stephen Cook establishing the concept of NP-completeness, and independent related work by mathematician Leonid Levin. If P equals NP, every one of the many known NP-complete problems, including numerous practically important scheduling, optimization and cryptographic problems, would have an efficient algorithmic solution; if P does not equal NP, as most computer scientists suspect based on decades of failed attempts to find such algorithms, an inherent gap exists between verifying and finding solutions for these problems. The Clay Mathematics Institute named P versus NP one of its seven Millennium Prize Problems in 2000, offering a one-million-dollar prize for a correct proof either way, and the question remains open, unresolved by any accepted proof, as of the early 2020s.