P vs NP is widely regarded as the most important unsolved problem in computer science. The Clay Mathematics Institute states the question simply: “If it is easy to check that a solution to a problem is correct, is it also easy to solve the problem?” Here P is the class of problems whose solutions are easy to find, and NP is the class whose solutions are easy to check.
The Clay Institute illustrates the gap with a housing example. Suppose a dean must place one hundred of four hundred students in dormitory rooms, given a list of pairs of students who cannot share housing. Checking whether a proposed list of one hundred names satisfies all the constraints is straightforward, but generating such a list from scratch appears to be completely impractical because the number of possible groupings is astronomically large. The P vs NP question asks whether that apparent gap between checking and finding is real.
According to the Clay Institute, Stephen Cook and Leonid Levin formulated the problem independently in 1971. The Clay page links to an official problem description written by Cook himself. The problem is one of the seven Millennium Prize Problems, each carrying a one million dollar award for a correct solution.
The Stanford Encyclopedia of Philosophy notes that although it “seems clear that P is strictly contained in NP” - the consensus expectation that P does not equal NP - this inequality has never been proved. A proof either way would reshape cryptography, optimization, and our understanding of what computers can efficiently do.