P versus NP

Does every problem whose solution can be verified quickly (in polynomial time) also admit a polynomial-time algorithm that finds the solution? This is the central open question of theoretical computer science and a Millennium Prize problem.

Most researchers believe P ≠ NP, but no proof is known in either direction. A constructive proof that P = NP would break virtually all modern cryptography; a proof that P ≠ NP would formalise the intuition that creativity is harder than verification.