NP-Completeness

Only applies to decision problems.

P:  Problems that can be answered YES/NO on a regular Turing Machine in polynomial time.

NP:  Problems that can be answered YES/NO on a nondeterministic Turing Machine in polynomal time.

P = NP:  Unknown, possibly the most important unsolved problem in theoretical computer science.

polynomial-time reduction:  If A and B decision problems, a polynomial-time reduction from A to B is an algorithm that runs in polynomial time that takes valid input for A and produces valid input for B, such A on A's input gives the same answer that B gives on B's input.

This means that if I have a good algorithm for B, I also have a good algorithm for A:  take A's input, convert it to B's input, run B on that input, I have my answer.

NP-Completeness:  A decision problem is NP-Complete if
1.  The problem is in NP.
2.  Every single problem in NP can be reduced to our given problem with a polynomial-time reduction.

So, if a problem A is NP-Complete and SOMEHOW I can solve it in polynomial time, then I can solve ANY problem in NP in polynomial time:  I use the reduction to convert that input to A's input (polynomial time) and then I solve A (also takes polynomial) time.  So, if ANY NP-Complete problem can be solved in polynomial time, then P=NP.  If P!=NP then NONE of the NP-Complete problems can be solved in polynomial time.

So, how do you prove that every single problem in NP can be reduced to any specific problem to prove NP-Completeness on that problem.

Well, turns out you only have to do it once.

Cook's Theorem:  SATISFIABILITY (or SAT) is NP-Complete.

This is the satisfiability problem:  Given a disjunction of conjunctions

(P & Q & R) v (~R & P & ~S & T & ~Q) v ...

Is there any possible assignment of truth values to the variables in this expression that will make the whole thing true?

What Cook did to reduce every single problem in NP to SAT is that his argument was based on the Turing Machine that existed for any specific problem in NP.  And he translated the states and transitions of that Turing machine to a logical statement.  A nondeterministic machine has a large but finite number of transitions at any given point, if any valid path makes to YES, then the answer is YES.  Along the lines, if any one of disjuncts in a logical statement is true, then the answer is true.  And it is in this way that Cook translated the Turing Machine to logical statement, knowing that the TM gave a YES answer iff the logical statement is true.

So, we now that SAT is NP-Complete.

Now, if you have problem A and you can reduce a known NP-Complete problem to problem A, then A is also NP-Complete (if A is also in NP):
Take any problem in NP, reduce it to the known NP-Complete problem, then reduce that to A.  Ta dah.  You've now reduced every problem in NP to A.

One of the early problems that SAT reduced to was 3-SAT.  3-SAT is exactly like SAT except that each disjunct contains EXACTLY 3 conjuncts.

(P & Q & ~R) v (Q & ~S & T) v ...

So, over the course of several decades we now have a slow slew of these NP-complete problems, covering wide areas of computer science.  What they all have in common is that we can't really solve any of them yet other than trial and error.

Three common NP-Complete problems that people refer to a lot.

HAMILTONIAN CYCLE.  Given a graph G=(V,E), is there a cycle that visits every vertex exactly once, returning to its starting point.

CLIQUE.  Given a graph G=(V,E) and an integer k, are there k vertices in the graph somewhere such each vertex is directly connected to the other k-1.

PARTITION.  Given a "set" of positive integers.  (I put "set" in quotes because repeats are allowed.)  Is there a way to partition the set into two sets such that the sets are equal in sum.