Class Note for CMPSCI 601 at UMass(42)
Class Note for CMPSCI 601 at UMass(42)
Popular in Course
Popular in Department
This 19 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 23 views.
Reviews for Class Note for CMPSCI 601 at UMass(42)
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 Recall From Last Time Lecture 17 FirstOrder Logic A vocabulary to talk about a par ticular type of domain formulas with atomic predicates boolean operators and quanti ers Fitch A proof system including the rules we had for boolean operators plus new rules for identity and quanti ers Main Theorems 0 Soundness Lecture 14 If P l Q in Fitch and M Pthenl Q 0 Completeness Lecture 15 If P l Q meaning that Q is true in any model where P is true then P l Q in Fitch 0 Compactness Lecture 16 If every nite subset of F has a model then P has a model 0 Incompleteness Lecture 16 Any re set of sen tences F in the language of number theory either con tains some statement that is false in N or cannot prove some statement that is true in N Relating Logic to Computability We observed that it is easy certainly primitive recursive to test whether an alleged proof is valid according to the rules of Fitch Corollary to Completeness F90 lt I l go i so lt2 i so FOVALID FOTHEOREMS Note that FOVALID and FOTHEOREMS are state ments that are true in any model of the given vocabu lary While we constructed a special model where every statement was either provably true or provably false this is not true in general An FOVALID statement about graphs would be true for all graphs but most interesting statements are true for some graphs and not for others Theorem 171 FOTHEOREMS is re complete Proof We have already seen that FOTHEOREMS is re because we can semidecide Whether a formula 5 is a theorem by searching all strings in parallel to see Whether any is a proof of 5 Recall that the language K is represented by a bounded formula 90K nEK lt N Kn lt NTl 90Kn n E K lt NT gt 90Kn E FOTHEOREMS We have thus shown that K g FOTHEOREMS by de n ing f so that f n NT gt WW A Note that this function is only wellde ned because NT is a nite set of formulas CMPSCI601 Back t0 Complexity Classes Lecture 17 De nition A set A g 2 is in DTIMEtn iff there exists a deterministic multitape TM M and a constant c such that lA M E w E 2 Mw 1 and 2 Vw E 2 Mw halts Within 01 steps De nition A set A g 2 is in DSPACEsn iff there exists a deterministic multitape TM M and a constant c such that lA M and 2 Vw E 2 Mw uses at most 01 worktape cells The input tape is considered readonly and not counted as space used L E DSPACElogn P s DTIMEn0lt1gt s lDTIMEW PSPACE s DSPACEn0lt1gt E OCDSPACEW llC z 1 Theorem For any functions tn 2 n have 301 2 log n we DTIMEtn g DSPACEtn DSPACEsn g DTIME2O3 gt Proof Let M be a DSPACEsn TM let w E 2 let n W M M has at most 1Q n 0301 2y 1216800 lt 26 800 possible con gurations Thus after 263 steps M w must be in an in nite loop A Corollary L g P g PSPACE NTIME E problems accepted by NTMS in time tn NTIMEn0lt1gt 2 f0 NP NTIMEM ll Theorem For any function tn DTIMEtn g NTIMEtn g DSPACEtn g DTIME20lttltngtgt Corollary L C P C NP g PSPACE CMPSCI601CM730A The Function Class FC Lecture 17 For any complexity class C de ne F C the total polynomially bounded functions computable in C as follows EWWXWSCN S klwlk Fm h i Z gt Z and bitgraphUl E C bitgraphh 92239 b biti ofha is b Idea f E FC iff l f is polynomially bounded and 2 biti of f w is uniformly computable in C and coC We rule out functions that are not polynomially bounded because we want to be able to de ne the complexity class in terms of either the input length or the output length CMPSCI 601 NSPACE Lecture 17 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 Remember that in g graphs always have constants for the vertices s and t We observed earlier that REACH is in the class P be cause we can depth rst search G starting from s in time 06 0012 and see whether we ever encounter t This algorithm is not spaceef cient however as we need 0n space to keep track of whether each vertex has been vis ited Proposition REACH 65 NL NSPACElog 71 Proof Let n W and let a and b be variables ranging oververuces boolean reach bS for int cO c lt n c if bt return true ab b nondeterministicChoice if not edgeab return false return false This algorithm might return true if the input graph is in REACH and cannot return true if it is not It uses three variables of Olog 71 bits each and thus puts the lan guage REACH in the class NSPACElog Q 10 De nition 172 A problem T is complete for a complex ity class C iff l T E C and 2 VA 6 CA g T A We have to rede ne the notion of reduction used in de n ing the g symbol Total recursive reductions would make the concept of NPcompleteness unreasonable NPcompleteness is usually de ned in terms of reduc tions in the class F P functions computable in polyno mial time But we re going to want to talk about lan guages complete for P and NL so we rede ne our re ductions to be in F We re most interested in natural complete problems for these classes meaning problems that someone might have posed other than as examples of complete problems It turns out that the natural complete problems we will see remain complete under any reasonable notion of reduc t10n ll Theorem 173 REACH is complete for NL Proof Let A 65 NL A N uses clogn bits of worktape Input 21 n w w r gt CompGraphNw V Est V ID ltqhp q E StatesNh g n p g cllognl s initial ID t accepting ID An accepting computation of N corresponds exactly to a path through the con guration graph from the start con guration to the accepting con guration following an edge for each computation step 12 readonly input W h worktape p lt c10gn gt C0mpGraphNw V Est V ID ltqhp q E StatesNh g n p g C Og l E ID1ID2 1 ID1w N gtID2w s initial ID t accepting ID 13 Claim w E A lt w E N lt CompGraphNw E REACH Corollary 174 NL g P Proof We say that REACH E P P is closed under logspace reductions That is BeP AgB gt AeP Q 14 CMPSCI 601 Hierarchy Theorems Lecture 17 De nition 175 Function f N gt N is Cconstructible if the map 1 gt f n is computable in the complexity class C f For exam ple a function f is DSPACEconsti39uctible if the func tion f can be deterministically computed from the in put 1 using space at most Q Fact 176 All reasonable functions greater than or equal to log n are DSPACEconstructtble and all reasonable functions greater than or equal to n are DTIME constructtble 15 The Four Hierarchy Theorems Theorem 177 ff is a Cconstructible function C is DSPACE NSPACE DTIME 0r NTIME ana is su ciently smaller than f then C is strictly con tained in C f 901 su ciently smaller than f means teem f n for C DSPACE NSPACE NTIME ana gltngtlogltgltngtgt 1 n 0 for C DTIME 16 We ll only prove one of these four in lecture Theorem 178 Space Hierarchy Theorem Let f 2 logn be a space constructible function If L r11 ltgt10fltnf0 Then DSPACEgn g DSPACEfn Proof Construct following DSPACEf machine D Input w n w 1 Mark off 6f tape cells f space constructible 2 Simulate using space 3 f n time 3 23fln 3 if M10011 needs more space or time then accept 4 else if M10011 accept then reject 5 else accept Mww reject space to simulate counter 3fn WM 17 Claim D e DSPACEfn DSPACEgn Clearly D E DSPACEf by the construction Suppose that D E DSPACEgn Let D where Mw uses cgn space Choose a number N such that Vn gt N cgn lt f Choose a string 211 such that M10 and Mw compute the same function and that 1211 gt N Add useless states to Mm for example On input w D successfully simulates szw in 3f space and 23fln time But now we have a contradiction of E D lt 20 g er lt 20 g mum lt2 2039 g up 18 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 19
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'