6.006 Lecture 23: Computational Complexity

Lecture 23: Computational Complexity Lecture Overview • P, EXP, R • Most problems are uncomputable • NP • Hardness & completeness • Reductions Definitions: • P = {problems solvable in polynomial (nc ) time} (what this class is all about) c • EXP = {problems solvable in exponential (2n ) time} • R = {problems solvable in finite time} “recursive” [Turing 1936; Church 1941] } computational difficulty } P EXP } R uncomputable/ undecidable P C EXP C R = = Examples • negative-weight cycle detection ∈ P • n × n Chess ∈ EXP but ∈ /P Who wins from given board configuration? • Tetris ∈ EXP but don’t know whether ∈ P Survive given pieces from given board. 1 Halting Problem: Given a computer program, does it ever halt (stop)? • uncomputable (∈ / R): no algorithm solves it (correctly in finite time on all inputs) • decision problem: answer is YES or NO Most Decision Problems are Uncomputable • program ≈ binary string ≈ nonneg. integer ∈ N • decision problem = a function from binary strings (≈ nonneg. integers) to {YES (1), NO (0)} • ≈ infinite sequence of bits ≈ real number ∈ R |N|  |R|: no assignment of unique nonneg. integers to real numbers (R uncountable) • =⇒ not nearly enough programs for all problems • each program solves only one problem • =⇒ almost all problems cannot be solved NP NP = {Decision problems solvable in polynomial time via a “lucky” algorithm}. The “lucky” algorithm can make lucky guesses, always “right” without trying all options. • nondeterministic model: algorithm makes guesses & then says YES or NO • guesses guaranteed to lead to YES outcome if possible (no otherwise) In other words, NP = {decision problems with solutions that can be “checked” in polynomial time}. This means that when answer = YES, can “prove” it & polynomial-time algorithm can check proof Example Tetris ∈ NP • nondeterministic algorithm: guess each move, did I survive? • proof of YES: list what moves to make (rules of Tetris are easy) 2 } computational difficulty P }} NP EXP } uncomputable/ undecidable R P 6= NP Big conjecture (worth $1,000,000) • ≈ cannot engineer luck • ≈ generating (proofs of) solutions can be harder than checking them Hardness and Completeness Claim: If P = 6 NP, then Tetris ∈ NP - P [Breukelaar, Demaine, Hohenberger, Hoogeboom, Kosters, Liben-Nowell 2004] Why: Tetris is NP-hard = “as hard as” every problem ∈ NP. In fact NP-complete = NP ∩ NPhard. EXP-complete }} NP-hard EXP-hard NP-complete } P computational difficulty Tetris Chess }} NP EXP uncomputable/ undecidable R 3 Similarly Chess is EXP-complete = EXP ∩ EXP-hard. EXP-hard is as hard as every problem in EXP. If NP = / EXP \ NP. Whether NP = 6 EXP, then Chess ∈ 6 EXP is also an open problem but less famous/“important”. Reductions Convert your problem into a problem you already know how to solve (instead of solving from scratch) • most common algorithm design technique • unweighted shortest path → weighted (set weights = 1) • min-product path → shortest path (take logs) [PS6-1] • longest path → shortest path (negate weights) [Quiz 2, P1k] • shortest ordered tour → shortest path (k copies of the graph) [Quiz 2, P5] • cheapest leaky-tank path → shortest path (graph reduction) [Quiz 2, P6] All the above are One-call reductions: A problem → B problem → B solution → A solution Multicall reductions: solve A using free calls to B — in this sense, every algorithm reduces problem → model of computation NP-complete problems are all interreducible using polynomial-time reductions (same difficulty). This implies that we can use reductions to prove NP-hardness — such as in 3-Partition → Tetris Examples of NP-Complete Problems • Knapsack (pseudopoly, not poly) • 3-Partition: given n integers, can you divide them into triples of equal sum? • Traveling Salesman Problem: shortest path that visits all vertices of a given graph — decision version: is minimum weight ≤ x? • longest common subsequence of k strings • Minesweeper, Sudoku, and most puzzles • SAT: given a Boolean formula (and, or, not), is it ever true? x and not x → NO • shortest paths amidst obstacles in 3D 4 • 3-coloring a given graph • find largest clique in a given graph 5