P versus NP problem

In computational complexity theory, P is the class of decision problems solvable by a deterministic algorithm in polynomial time: the number of steps is bounded by a polynomial in the length of the input. NP is the class of decision problems for which a proposed positive answer can be verified in polynomial time, equivalently defined using nondeterministic polynomial-time computation. The P versus NP problem asks whether P = NP. Since a solution that can be found quickly can also be checked quickly, P is contained in NP; the unresolved issue is whether NP contains problems that cannot be solved in polynomial time.

Some problems have candidate answers that are straightforward to check, even when finding an answer seems difficult. For example, if given a proposed selection of students, it is easy to check whether the selection meets constraints on size and incompatible pairs. Finding a valid selection from scratch may require searching among many possibilities. This illustrates the intuition behind the question, but an apparent difficulty or an inefficient brute-force method is not proof that no polynomial-time algorithm exists.

A problem is NP-complete if it belongs to NP and every problem in NP can be reduced to it by an appropriate polynomial-time transformation. Such problems represent, in this formal sense, the hardest problems in NP. If any NP-complete problem has a polynomial-time algorithm, then every problem in NP does, establishing P = NP. Conversely, proving that even one NP-complete problem has no polynomial-time algorithm would establish P ≠ NP. The satisfiability problem was the first problem proved NP-complete, in independent work by Stephen Cook and Leonid Levin.

The problem matters both theoretically and practically. Many scheduling, planning, and optimization questions are related to computational problems in NP, and the difficulty of certain problems underlies important cryptographic assumptions. A constructive proof that P = NP would provide efficient algorithms for NP-complete problems, with potentially far-reaching effects; what those effects would be in practice would depend on the actual algorithms and their running times. A proof that P ≠ NP would show that some efficiently checkable problems cannot all be solved efficiently in the standard polynomial-time model.

P versus NP is an open problem. The Clay Mathematics Institute lists it among its Millennium Prize Problems. Stephen Cook and Leonid Levin formulated the question independently in 1971. The mathematical challenge is to prove a general statement about all possible algorithms, not merely to show that current methods or computers struggle with selected instances.