Complexity theory

The class NP consists decision problems with solutions that can be "checked" in polynomial time. Equivalently, it can also be defined as a set of decision problems solvable in polynomial time via a "lucky" algorithm. This is a nondeterministic model where an algorithm makes guesses and then says YES or NO.  The name "NP" stands for "nondeterministic polynomial time".

A problem is in the class NP-complete, if it is in NP and is as "hard" as any problem in NP. So NP-complete problems are the hardest problems in NP.

Examples of NP-complete problems:

• Knapsack (pseudopolynomial, O(nS) where n is number of items and S is the size of the knapsack)
• Traveling salesman problem
• SAT
• Tetris
• 3-coloring a given graph

MIT 6.006 notes: http://courses.csail.mit.edu/6.006/fall11/lectures/lecture23.pdf