1Class 24: Class 24: P=NP?P=NP?David EvansDavid Evanshttp://www.cs.virginia.edu/evanshttp://www.cs.virginia.edu/evanscs302: Theory of Computationcs302: Theory of ComputationUniversity of Virginia Computer ScienceUniversity of Virginia Computer SciencePS6 (the last one) is due Thursday, April 24.Protein model, Berger Lab UC BerkeleyRemaining Exam 2 comments now posted.2Lecture 24: P=NP?Final Exam• Scheduled by registrar: – Saturday, May 3, 9am-noon (exam is scheduled for 3 hours, but will be designed to take ≤ 1.5 hours)• No notes or books allowed– My sense from grading Exam 2 is people used their notes as a crutch, not helpfully– Enables “easier” questions and more partial credit• In class next Tuesday, I will hand out a “preview”of some of the exam questions and possibly discuss them3Lecture 24: P=NP?Final Exam Topics• Everything covered through this Thursday:– Exams 1 and 2 and comments– Problem Sets 1-6 and comments– Lectures 1-25– Sipser, Chapters 0-5, 7– Additional Readings: Aaronson (spring break), one of the NP-completeness papers• Roughly ⅓ Exam 1 material, ⅓ Exam 2 material, ⅓since Exam 2 (but many individual questions will combine material from multiple parts)4Lecture 24: P=NP?P = NP ?PNPPNPOption 2: P = NPOption 1: P ⊂ NP5Lecture 24: P=NP?Theological QuestionIf God exists (and is omnipotent), can she compute anything regular people cannot compute?Yes: P ⊂ NPBeing able to always guess right when given a decision makes you more powerful than having to try both.No: P = NPBeing able to always guess right when given a decision does not make you more powerful than having to try both.6Lecture 24: P=NP?NP-CompleteA language B is in NP-complete if:2. There is a polynomial-time reduction from every problem A ∈ NP to B.1. B ∈ NPBNPBNPIs NP-Complete a Ring or a Circle?27Lecture 24: P=NP?NP-CompletePNPPNPOption 2: P = NPOption 1: P ⊂ NPNP-C= NP-Complete ∪ TautologyTautology problemsA = {}; A = Σ*8Lecture 24: P=NP?NP-CompletePNP-COption 1a: P ⊂ NP, NP-C ∪∪∪∪ P ⊂ NPOption 1b: P ⊂ NP, NP-C ∪∪∪∪ P = NPPNP-CEither is possible9Lecture 24: P=NP?NP-CompleteA language B is in NP-complete if:2. There is a polynomial-time reduction from every problem A ∈ NP to B.1. B ∈ NPBNPBNPWhat does NP-Hard look like?HardNot necessary for NP-Hard10Lecture 24: P=NP?NP-Hard (if P ⊂ NP)PNP-COption 1a: P ⊂ NP, NP-C ∪∪∪∪ P ⊂ NPOption 1b: P ⊂ NP, NP-C ∪∪∪∪ P = NPNP-HardPNP-C11Lecture 24: P=NP?NP-Hard (if P = NP)PNPOption 2: P = NPNP-C≈ NP-CompleteNP-Hard = All Problems - {A = {}; A = Σ*}12Lecture 24: P=NP?NP-Hardness Recap• If P = NP:– To show a problem is NP-Hard: show for some input it outputs “true”, and for some input it outputs “false”• If P ⊂ NP:– To show a problem is NP-Hard: show that there is a polynomial-time reduction from some known NP-Complete problem to it– Showing a problem is NP-Hard means there is no polynomial time solution for it313Lecture 24: P=NP?Games and NP-Hardness14Lecture 24: P=NP?Papers from Last Class• (Generalized) Cracker Barrel Puzzle is NP-Complete• (Generalized) March Madness is NP-Hard– Is it NP-Complete also?• (Generalized) Minesweeper Consistency is NP-Complete• ... ?Are these special cases, or is there something about “interesting” games that makes them NP-Hard?What makes a “game” a game?16Lecture 24: P=NP?All “Interesting” Games?Initial Game StatePossible Moves...Winning StateWhat is a “winning path”?17Lecture 24: P=NP?Recall: Class NPA language is in NP if and only if it is decided by some nondeterministic polynomial time Turing MachineA language is in NP if and only if it has a corresponding polynomial time verifierThat is, there is a certificate that can prove a string is in the language which can be checked in polynomial time.18Lecture 24: P=NP?Game Certificate• Given a path through a game, can you check if it is a valid winning path in polynomial time?def verify(Path p):return isInitialState(p[0])&& isWinningState(p[-1])&& allMovesValid(p)def allMovesValid(Path p):if (p.length <= 1) return true;return isValidMove(p[0], p[1]) && allMovesValid(p[1:])419Lecture 24: P=NP?(One-Player) Games in NP• The maximum number of moves is polynomial in the size of the game• There is a polynomial-time procedure for checking a move (state, state pair) is valid• There is a polynomial-time procedure for checking a position is a winnerHow could a game be outside NP?e.g., Hex, Sokoban??20Lecture 24: P=NP?Games in P• The number of possible moves or the number of moves you need to lookahead to pick the right move, does not scale with the size of the gameThere is a polynomial-time function from the game state to the correct move: don’t need to consider deep paths to select the right move21Lecture 24: P=NP?NP-Complete One-Player Games• In NP: polynomial-time certificate• Polynomial-time reduction from 3SAT (or any other NPC problem) to the gameEssentially: no way to know if a move is correct without looking ahead all the way to the end.All “fun” one-player games are NP-Complete:Games inside P are too easy (once you solve them always win)Games outside NP are too hard But…we actually play finite versions of these games (in TIME(1))22Lecture 24: P=NP?Reduction Proofs23Lecture 24: P=NP?Reducing Reduction Proofs• Conjecture: A has some property Y.• Proof by reduction from B to A:– Assume A has Y. Then, we know there is an M that decides A.– We already know B does not have property Y.– Show how to build S that solves B using M.• Since we know B does not have Y, but having Swould imply B has Y, S cannot exist. Therefore, M cannot exist, and A does not have Y.24Lecture 24: P=NP?Undecidability Proofs• Conjecture: A has some property Y.• Proof by reduction from B to A:– Assume A has Y. Then, we know an M exists.– We already know B does not have property Y.– Show how to build S that solves B using M.• Since we know B does not have Y, but having S would imply Bhas Y, S cannot exist. Therefore, M cannot exist, and A does not have Y.Undecidability:Y = “can be decided by a TM”B = a known undecidable problem (e.g., ATM, HALTTM, EQTM, …)M = “a TM that decides A”525Lecture 24: P=NP?NP-Hardness Proofs• Conjecture: A has some property Y.• Proof by reduction from B to A:– Assume A has Y. Then, we know an M exists.– We already know B does not have property Y.– Show how to build S that solves