MIT OpenCourseWare http ocw mit edu 6 080 6 089 Great Ideas in Theoretical Computer Science Spring 2008 For information about citing these materials or our Terms of Use visit http ocw mit edu terms 6 080 6 089 GITCS DATE Lecture 12 Lecturer Scott Aaronson 1 Scribe Mergen Nachin Review of last lecture NP completeness in practice We discussed many of the approaches people use to cope with NP complete problems in real life These include brute force search for small instance sizes cleverly optimized backtrack search xed parameter algorithms approximation algorithms and heuristic algorithms like simulated annealing which don t always work but often do pretty well in practice Factoring as an intermediate problem between P and NP complete We saw how factoring though believed to be hard for classical computers has a special structure that makes it di erent from any known NP complete problem coNP 2 Space complexity Now we will categorize problems in terms of how much memory they use De nition 1 L is in PSPACE if there exists a poly space Turing machine M such that for all x x is in L if and only if M x accepts Just like with NP we can de ne PSPACE hard and PSPACE complete problems An interesting example of a PSPACE complete problem is n by n chess Given an arrangement of pieces on an n by n chessboard and assuming a polynomial upper bound on the number of moves decide whether White has a winning strategy Note that we need to generalize chess to an n by n board since standard 8 by 8 chess is a nite game that s completely solvable in O 1 time Let s now de ne another complexity class called EXP which is apparently even bigger than PSPACE De nition 2 Deterministic f n Time denoted DTIME f n is the class of decision problems solvable by a Turing machine in time O f n De nition 3 Exponential Time denoted EXP equals the union of DT IM E 2p n over all poly nomials p Claim 4 P SP ACE EXP 12 1 EXP PSPACEComplete PSPACE NPComplete NP P Figure by MIT OpenCourseWare Figure 1 A general picture that we believe Proof Just like in problem set 2 In order for the machine to halt any con guration must be visited at most once Assuming an upper bound of p n on the number of tape squares there are 2p n possible settings of 0 s and 1 s on the tape p n possible locations for the Turing machine head and s possible states for the head So an upper bound on number of steps is 2p n p n s which is exponential in p n Claim 5 P P SP ACE Proof Obviously a P machine can t access more than a polynomial number of memory locations Claim 6 N P P SP ACE Proof Enumerate all possible polynomial size proofs Remark Does NP PSPACE Just like P vs NP this is a longstanding open problem It s conjectured that they re di erent De nition 7 LOGSPACE is the class of decision problems solvable by a Turing machine with O log n bits of memory Remark But isn t the input already n bits A technicality The LOGSPACE machine has read only access to the input It s only the read write memory that s logarithmically bounded Claim 8 LOGSP ACE P 12 2 Proof Same as Claim 4 except scaled down by an exponential There are at most s2c log n c log n nO 1 possible con gurations of a Turing machine with c log n tape squares Remark Does LOGSPACE P Another longstanding open problem Again conjecture is that they are di erent We can prove LOGSP ACE P SP ACE using a Space Hierarchy Theorem similar to the Time Hierarchy Theorem that we saw in Lecture 7 As usual it s not hard to prove that more of the same resource time space etc provides more computational power than less of it The hard part is to compare di erent resources like time vs space or determinism vs nondeterminism 3 Why do we believe P N P if we can t prove it Hardness of solving NP complete problems in practice the empirical case There are vastly easier problems than NP complete ones like factoring that we already have no idea how to solve in P As Go del argued P NP would mean mathematical creativity could be automated God would not be so kind We know that LOGSP ACE P SP ACE But this means either LOGSP ACE P or P N P or N P P SP ACE And if one is true then why not all three Incidentally let me tell you one of the inside jokes of complexity theory Let LINSPACE be the set of problems solvable in linear space Then one of the very few separations we can prove is that LIN SP ACE P Why Well suppose P LIN SP ACE Then P P SP ACE also Why Pad the inputs But that means LINSPACE PSPACE which is ruled out by the Space Hierarchy Theorem The punchline is while we know P and LINSPACE are di erent we have no idea which one is not contained in the other one or as is most likely whether neither is contained in the other one We just know that they re di erent 4 Why is it so hard to prove P N P Because P NP Because there really are lots of clever non obvious polynomial time algorithms Any proof that 3SAT is hard will have to fail to show 2SAT is hard even though the handwaving intuition seems the same for both there are 2n possible solutions and clearly each one takes at least constant time to check Simple as it seems this criterion already rules out almost every amateur P N P proof in Prof Aaronson s inbox Let NPSPACE Nondeterministic PSPACE be the class of problems solvable by a PSPACE machine that can make nondeterministic transitions Then by analogy to P N P you might conjecture that P SP ACE N P SP ACE But Savitch s Theorem shows that this conjecture is false PSPACE NPSPACE So any proof of P N P will have to fail when the polynomially bounded resource is space rather than time 12 3 The Baker Gill Solovay argument Techniques borrowed from logic and computability theory like the ones used to prove the Time Hierarchy Theorem all seem to relativize In other words they all seem to go through without change if we assume there s a magical oracle in the world that solves some problem for free As an example recall how the proof of unsolvability of the halting problem could easily be adapted to show the unsolvability of the Super Halting Problem by Super Turing Machines By contrast any solution to the P vs NP problem will have to be non relativizing In other words it will have to be sensitive to whether or not there s an oracle around Why Well because …