Class Note for CMPSCI 601 at UMass(30)
Class Note for CMPSCI 601 at UMass(30)
Popular in Course
Popular in Department
This 13 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 13 views.
Reviews for Class Note for CMPSCI 601 at UMass(30)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CMPSCI 601 Complexity Classes Lecture 16 De nition A set A Q 23 is in DTIMEtn iff there exists a deterministic multitape TM M and a constant c such that lA M E w E 2 l and 2 V11 6 2 halts Within 01 steps De nition A set A Q 23 is in DSPACEsn iff there exists a deterministic multitape TM M and a constant c such that lA M and 2 V11 6 2 uses at most 01 worktape cells The input tape is considered readonly and not counted as space used L E DSPACElogn P DTIMEn0lt1gt lDTIMEW PSPACE E DSPACEn0lt1gt E O lDSPACEW Theorem For any functions tn 2 n have 302 2 log n we 9 DTIMEtn Q DSPACEtn DSPACEsn g DTIME208 Proof Let M be a DSPACEsn TM let w E 23 let n M has at most 162 71 csm 2k1z1csltngt lt 20 800 possible con gurations Thus after 265 steps M must be in an in nite loop A Corollary L C P g PSPACE NTIME E problems accepted by NTMS in time tn NP NTIMEn0lt1gt NTIMEW 21 Theorem For any function tn DTIMEtn g NTIMEtn g DSPACEtn Q DTIME20lttltngtgt Corollary L C P C NP g PSPACE CMPSCI 601 NSPACE Lecture 16 NSPACEsn is the set of problems accepted by NTMs using at most Osn space on each branch 9 n AM ooooooooooooowooooooooo tn 3n space on each branch De nition REACH is the set of directed graphs G such that there is a path in G from s to t 3 8 2 Proposition REACH E NL NSPACE10g n Proof Letn 21V a b 1 b s 2 fore 1to n do 3 ifb 2t then accept 4 a b 5 nondeterrninistically choose new I 6 if HEM b then reject 7 reject This algorithm accepts REACH in NSPACE10g Q 5 De nition 161 Problem T is complete for complexity class C iff l T E C and 2 VA 6 CA g T Reductions now must be in Q Theorem 162 REACH is complete for NL Proof Let A E NL A N uses clogn bits of worktape Input 21 n w 1 gt CompGraphNw VEst V ID q hpgt l q E StateSUVM S n 1291 S cllognl E ID1ID2 1 1mm 71mm 3 2 initial ID t accepting ID readonly input W h worktape p lt clogn gt C0mpGraphN w V E s t V ID q mm 1 q E StateSUVM S n 1291 S cflogni s 2 initial ID t accepting ID Claim 11 E A ltgt w E N ltgt CompGraphNw E REACH Corollary 163 NL g P Proof REACH E P P is closed under logspace reductions That is BEP AgB gt AEP Q CMPSCI 601 Hierarchy Theorems Lecture 16 Theorem 164 ff is a Cconstructible function C is DSPACE NSPACE DTIME 0r NTIME and if 902 is su iciently smaller than f then C is strictly con tained in C f 902 su iciently smaller f means limnm g 0 umnm 0 c DSPACE NSPACE NTIME c DTIME De nition 165 Function f N gt N is Cconstructible if the map 1 lgt f n is computable in the complexity class C f For exam ple a function f is DSPACEconstructible if the func tion f can be deterministically computed from the in put 1quot using space at most Q Fact 166 All reasonable functions greater than or equal to log n are DSPACEconstructible and all reasonable functions greater than or equal to n are DTIME constructible Theorem 167 Space Hierarchy Theorem Let f 2 logn be a space constructible function If M wigglcmz 0 Then DSPACEgn DSPACEfn Proof Construct following DSPACEf machine D Input 11 n 1 Mark off 6f tape cells f space constructible 2 Simulate using space 3 f n time 3 2mquot 3 if needs more space or time then accept 4 else if accept then reject 5 else accept reject space to simulate counter 3f n 3f n 10 Claim D E DSPACEfn DSPACEgn D E DSPACEf by construction Suppose D E DSPACEgn Let D Mu uses cgn space Choose N st V72 gt Ncgn lt Choose 11 1111 gt N On input 111 D successfully simulates Mww in 3f space and 2mquot time 21139 E D ltgt w39 gZ Mw ltgt 71 ltgt w39 gZ D gtlt ll mm Arlthmetlc H1erarchy W c0re Recursive 139 e re complete Primitive Recursive EXPTIME PSPACE c0NP PolynomialTime Hierarchy complete c0NP NP NP 1 c0NP NP complete quottruly feasiblequot NC NC2 logCFL SAC NSPACE log n 3 DSPACE log n Regular LogarithmicTime Hierarchy 12 CMPSCI601CM730A The Function Class FC Lecture 16 For any complexity class C de ne F C the total polynomially bounded functions computable in C as follows 3kWlhl S klwlk Flc 2 h i E gt Z and bitgraphh E C bitgraphh 2 92239 1 bitz ofha is b Idea f E FC iff l f is polynomially bounded and 2 bitz of f is uniformly computable in C and coC l3
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'