NP-Completeness

If a, b, c are integers >= 1  and n is an integer >= 3, does the equation a^n + b^n = c^n have any solutions?  Pierre de Fermat said no.
In 1993, Andrew Wiles (Princeton University) solved it.  The answer is no.

Does P equal NP is the most important unsolved problem in theoretical computer science.  Most computer scientists (including me) believe that P != NP.  But there are a few that do (and there are reasons one might).

P and NP are sets or classifications of "problems".  More precisely, they are classifications of "decision" problems.

A decision problem is a problem whose answer is a single bit.  True/False On/Off Yes/No 1/0.  (The input might be anything but the output is a single bit.)

A problem is in P if there is an algorithm solving it that runs in O(n^k) time where k is a nonnegative integer.  If it takes n^2 time or n^3 time or n^100 time or n^googol time, it's still a polynomial-time algorithm and so it is in P.

Traditionally, the runtime of these algorithms are based on how quickly they run on a Turing Machine, whereas most people describe their algorithms using some form of a RAM model.  However, you can prove mathematically that the polynomial algorithms on RAM are also polynomial on a Turing Machine.

To be clear, a decision problem is in P if there is a polynomial-time algorithm that solves it...even if we don't know what that algorithm is!

Now, NP is something a bit more abstract.  NP does NOT stand for "non-polynomial".  It stands for "nondeterministic polynomial."

A couple of ways to envision this.  Imagine a programming language has a "nondeterministic" command.

NONDET
	STMT1;
	STMT2;
	STMT3;
	...
	STMTN;
END NONDET

The program runs only one of the statements.  Which one?  The one that gets the correct answer!  Because it's smart enough to know which one that is!

Another way to look at nondeterminism:  An infinite number of parallel machines.  When they reach a nondeterministic moment, some will go one way, some will go the other.  One of them will by chance happen to hit upon the correct sequence of statements that will yield the answer.

Think of solving a maze.  If I put an infinite number of robots at the beginning of the maze and have them choose randomly which path to take at every junction point.  Some will go around in circles.  Some will eventually make it to the finish line.  And some will choose right every time and just go directly to the finish line.  And the robots who get there first get to state the runtime.  The runtime is that of the fastest robot to get there.

So, NP is the classification of decision problems that can be solved in polynomial time on a nondeterministic machine.  So, if I have an infinite number of machines taking all possible branches, is there SOME branch a machine could take that would compute the answer in polynomal time?

Naively, one would think that "intelligent randomness" is such a useful tool to have that there would be a host of problems with a solution that one could stumble onto in polynomial time but would take longer than a single machine trying those paths one at a time.  This is what most computer scientists believe (including me), but it's never been proven.

P is a subset of NP.  Anything in polynomial time can OBVIOUSLY done in polynomial time nondeterministically.

Is NP a subset of P?  That's the question.

And so, NP-Completeness is a mechanism for classifying problems based on the distinction between P and NP.  If a problem is NP-Complete, it might be possible to do it in P time, but no one has ever done so.  If your boss, "I need a fast program to solve this problem.  Are you smart enough to do it?"  "No, I'm not, but then, no other computer scientist is, either, including really famous ones."