P vs NP (P = NP or P ≠ NP)

This one is the most famous problem in computer science, and one of the most important outstanding questions in the mathematical sciences. In fact, the Clay Institute is offering one million dollars for a solution to the problem (Stephen Cook’s writeup on the Clay website is quite good).

It’s clear that P is a subset of NP. The open question is whether or not NP problems have deterministic polynomial time solutions. It is largely believed that they do not.

The best book on the subject is Computers and Intractability by Garey and Johnson.