Class Note for CMPSCI 601 at UMass(49)
Class Note for CMPSCI 601 at UMass(49)
Popular in Course
Popular in Department
This 18 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 18 views.
Reviews for Class Note for CMPSCI 601 at UMass(49)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 02/06/15
CMPSCI 601 Recall From Last Time Lecture 18 Theorem REACH is complete for NL Proof w E N ltigt CompGraphNw E REACH A Space Hierarchy Theorem Let f 2 logn be a space constructible function If 901 ll 1 0 n gtoc Then DSPACEgn DSPACEfn Proof Diagonalize against all machines using space 3f and time 23f A We stated but did not prove the similar Time Hierarchy Theorem CMPSCI 601 NSPAC E VS DSPAC E Lecture 18 How well can we simulate nondeierministic space with deterministic space We know one way to do it already Proposition 181 NSPACE8n g NTIME20S g DSPACE2Osn In fact we can do far better as we ll now show We have two algorithms now for reachability 0 DFS etc which are good for time 7101 but bad for space 001 and 0 Nondeterministic search which is good for space 0log but not a real algorithm at all because of the nonde terminism How do we attack reachability if space is the main con cem Theorem 182 REACH E DSPACElogn2 Proof De ne PATH1 y k as there is a path from vertex 1 t0 vertex 3 of length k or less G E REACH ltgt G P PATHstn PATHGW 1 E 5021 V Etay PATHy2d E 32PATHZd PATHZyd This gives us a recursive algorithm for PATH How much space does it use We determine the space usage with a recurrence Sn d space to check paths of distance d in graphs with n nodes 5010 01 50119 O10gnSnk2 and s0 50 010gn2 7mmcmbemmgmo mammwemmymmhdgmmm for REACH ef cient for deterministic space but lousy ntnne boolean isPath vertex x vertex y int dist if x y return true if dist 1 return edgex y else for vertex u O u lt n u if isPath x u dist2 ampamp isPath u y dist dist2 return true return false Thecdlpathstn lreunamtoadq hofahnom log 71 Each recursive call needs Olog 71 bits on the stack But the running time may be as bad as nlog since there are in effect log n nested loops YKn D 0U Tnk OnTnk2 and so TTnn n0WW Corollary 183 Savitch s Theorem For 3n 2 log n DSPACEsn Q NSPACEsn Q DSPACEsn2 Proof Let A e NSPACEsn A N w E A ltgt CompGraphN w E REACH 1w n 1C0mpGraphNw1 20sn TeSting if ComPGraphN w E REACH takes space logC0mpGraphNmm2 10g208n2 08n2 From w build C0mpGraphN w in DSPACEsn A Corollary 184 PSPACE NPSPACE CMPSCI 601 ImmermanSzelepcs nyi Thm Lecture 18 Along with regular languages and CFL s there is another oldtime complexity class called the contextsensitive cm guages that turns out to be NSPACEn It was asked whether this class is closed under complement like the regular languages or not like the CFL s Since the gen eral intuition was that it was not no one looked for a proof that it was The problem remained open for about twenty years In 1987 two researchers Neil Immerman in the US and Richard Szelepcsenyi in Slovakia simultaneously found a proof that nondeterministic space classes are closed under complement Not only that the proof is easy to present The reason for the simultaneity is probably that a series of results just before this began to suggest that the result might be true Neil reports that he got the basic idea of the proof while walking his dog Theorem 185 REACH E NL Proof Fix the graph G Nd H22 1 v reachable from s using 3 d edges Claim The following predicates are each in NL l DISTId distancesc g d 2 NDIST C d m ifm Nd then DISTc d Proof 1 Guess the path of length 3 d from s to c 2 Guess m distinct vertices v1 vm with each vi y 19 and guess paths showing DISTm d for each 239 A Claim We can compute Nd in NL What does compute mean We de ne a nonde terrninistic procedure that either a outputs the correct value of Nd or b fails to output anything There must be at least one path on which a occurs Proof By induction on d Base case No 1 whatever the graph Inductive step Suppose we are on a path that has reached a value of Nd which by the 1H is correct The following pseudoJava code returns the correct value of Nd if it makes the right guesses and rejects otherwise intc O for int vO v lt n v if guessBoolean if DISTVdl c else reject else verify lDISTvd1 for int 20 2 lt n z if NDISTzdNd break if zlv ampamp ledgezv break reject return c The right guesses are true for 22 s that are Within dis tance d 1 of s and false for the others Correct guesses can be veri ed and wrong guesses cause the whole procedure to reject GEE REACH e NDISTtnNn 4s 10 Corollary 186 ImmermanSzelepcs nyi Theorem Let 3n 2 log n Then NSPACEsn coNSPACEsn Proof Let A E NSPACEsn A N w E A ltgt CompGraphN w E REACH W n 1CompGraphN W1 20ltsltngtgt Testing Whether CompGraphN w is in REACH with a nondeterministic procedure takes space log1C0mpGraphNw1 log208n 08n 11 CMPSCI 601 Review of Reductions Lecture 18 De nition 187 We say that S is reducible to T S g T iff 3 f E FL such that Vw E N w E S ltigt fw E T Q A0717 n 1 Claim K g A0717 Proof De ne f as follows erase input if 1 then write 17 M n write n M else loop nEK ltgt Mnnl 12 ltgt Mfn0 I 17 A Why is this reduction in FL Given a number n we need to write code for a TM that prints 71 runs Mn on it and then either writes 17 or loops We are limited to space that is logarithmic in the length of the binary number 71 But the print 71 part is going to be mostly a copy of the binary of n and we have assumed that the code of Mn is easily obtainable from the binary for n For example we could say that the binary either is the code for Mn in ASCII or n isn t the number of a TM The last part is only 01 bits of TM code 13 Theorem 188 Let C be one of the following complex ity classes L NL P NP coNP PSPACE EXPTIME PrimitiveRecursive RECURSIVE re core SupposeSgT IfT E C Then S E C That is each of these classes is closed under reductions 14 Proof Suppose that S g T and T E C We build aCmachine for S w E S ltigt fw E T logspace transducer C machine for T 15 There s actually a problem with this proof in the case where C is L or NL It s the same issue that came up in the extra credit of HW2 where we wanted to show that TIMES is in A Nontrivial Fact About Logspace Reductions Ing Banng CthenA C39 It looks obvious at rst but draw the picture of the two machines The output tape of the rst machine becomes the input tape of the second In the two original machines neither counts against the space bound but in the new machine this becomes a worktape Similarly the former output tape of our logspace trans ducer is now a worktape and we a priori need a work tape to store the n by n array of partial product bits when computing TIMES 16 Proving Transitivity Say we know that f reduces A to B and that g reduces B to 0 Clearly the reduction we want from A to C is h where hw gfw Then 11 E A iff hw E C39 The only problem is to show that h is in Here s how to compute M111 when w is the lengthn string on the readonly input tape Let 1 be f w and start computing g1 M111 When your computation needs a bit 1 of 1 however suspend that computation until you have calculated 1 from w and then continue At any given time you have the computation of g1 from 1 going which takes Olog Olog 11 space You also may be temporarily computing a bit of 1 from 11 which you get by carrying out the computation of f 111 using Olog 11 space until 1 is output at which time you take it and continue with the main computation This is a bit timeintensive but we don t care because we re concerned only with space The total space usage is Olog l7 Reductions are Useful for Lower Bounds If A is hard and A g B then we may conclude that B is hard Example B is de ned to be NPhard if for any 0 65 NP we have that C 3 B HA is NPhard and A g B B is seen to be NPhard by the transitivity of 3 Upper Bounds If B is easy and A g B then we may conclude that A is easy Example De ne easy to mean a member of C for any of the classes in the previous theorem 18