What's "P=NP?", and why is it such a famous 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?
Oh, and for extra credit, please post a proof of the statement's truth or falsehood. :)
Answer
P stands for polynomial time. NP stands for non-deterministic polynomial time.
Definitions:
Polynomial time means that the complexity of the algorithm is O(n^k), where n is the size of your data (e. g. number of elements in a list to be sorted), and k is a constant.
Complexity is time measured in the number of operations it would take, as a function of the number of data items.
Operation is whatever makes sense as a basic operation for a particular task. For sorting, the basic operation is a comparison. For matrix multiplication, the basic operation is multiplication of two numbers.
Now the question is, what does deterministic vs. non-deterministic mean? There is an abstract computational model, an imaginary computer called a Turing machine (TM). This machine has a finite number of states, and an infinite tape, which has discrete cells into which a finite set of symbols can be written and read. At any given time, the TM is in one of its states, and it is looking at a particular cell on the tape. Depending on what it reads from that cell, it can write a new symbol into that cell, move the tape one cell forward or backward, and go into a different state. This is called a state transition. Amazingly enough, by carefully constructing states and transitions, you can design a TM, which is equivalent to any computer program that can be written. This is why it is used as a theoretical model for proving things about what computers can and cannot do.
There are two kinds of TM's that concern us here: deterministic and non-deterministic. A deterministic TM only has one transition from each state for each symbol that it is reading off the tape. A non-deterministic TM may have several such transition, i. e. it is able to check several possibilities simultaneously. This is sort of like spawning multiple threads. The difference is that a non-deterministic TM can spawn as many such "threads" as it wants, while on a real computer only a specific number of threads can be executed at a time (equal to the number of CPUs). In reality, computers are basically deterministic TMs with finite tapes. On the other hand, a non-deterministic TM cannot be physically realized, except maybe with a quantum computer.
It has been proven that any problem that can be solved by a non-deterministic TM can be solved by a deterministic TM. However, it is not clear how much time it will take. The statement P=NP means that if a problem takes polynomial time on a non-deterministic TM, then one can build a deterministic TM which would solve the same problem also in polynomial time. So far nobody has been able to show that it can be done, but nobody has been able to prove that it cannot be done, either.
NP-complete problem means an NP problem X, such that any NP problem Y can be reduced to X by a polynomial reduction. That implies that if anyone ever comes up with a polynomial-time solution to an NP-complete problem, that will also give a polynomial-time solution to any NP problem. Thus that would prove that P=NP. Conversely, if anyone were to prove that P!=NP, then we would be certain that there is no way to solve an NP problem in polynomial time on a conventional computer.
An example of an NP-complete problem is the problem of finding a truth assignment that would make a boolean expression containing n variables true.
For the moment in practice any problem that takes polynomial time on the non-deterministic TM can only be done in exponential time on a deterministic TM or on a conventional computer.
For example, the only way to solve the truth assignment problem is to try 2^n possibilities.