Computational complexity

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

NP = {decision problems with solutions that can be "checked" polynomial time}

• It is based on the nondeterministic model where an algorithm makes guesses and then says YES or NO.
• Examples: Tetris

NP-hard = "as hard as" every problem in NP

NP-complete = NP \(\cap\) NP-hard

• Tetris is also NP-complete
• Other examples: knapsack, 3-Partition (given n integers, can you divide them into triples of equal sum?), traveling salesman problem, longest common subsequence of k strings, minesweeper, Sudoku, most puzzles, SAT, 3-coloring a given graph, find largest clique in a give graph