The P Versus NP Problem

$1 Million Millennium Problem #3 The P Versus NP Problem

~ the only Millennium Problem based on computers~

Hilbert's famous millennim list of 1900 asked for a proof that certain equations could not be solved by a computer. This proof was accepted by the general audience in 1970. Our century's challenge asks if computers can solve problems efficiently.

This problem falls into two categories. First, what tasks of type P can be solved efficiently on a computer? This implies there are tasks (type E) that could be solved, but would take millions of years to complete. Regretably, most practical applications fall somewhere in between. These tasks are labeled as the NP category. The Millinnium Problem asks for a proof answering whether P tasks andNP tasks are the same or different.

See Keith Devlin's "The Millennium Problems: The Seven Greatest Unsolved Puzzles of Our Time, Basic Books, 2002.