What's "P=NP?", and why is it such a famous question?

Question

The question of whether P=NP is perhaps the most famous in all of Computer Science. What does it mean? And why is it so interesting?

Answer 1

P is the set of all programs, algorithms, problems or Turing Machine programs that run in deterministic polynomial time. A deterministic machine is one that gives the same answer each time an algorithm is run with the same inputs.

NP is the set of all programs that run on nondeterministic Turing Machines or nondeterministic Finite State Automata in polynomial time. A nondeterministic machine is one that may transition from one state to zero or many states simultaneously. Intuitively, we say the machines make a 'guess' about which state is the one it needs to enter to achieve polynomial time.

No one has been able to prove whether P=NP. There have been large prizes offered to anyone who can solve this problem, and the problem has been around for quite some time.

I keep thinking of quantum computers when I think about nondeterminism...