### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for CMPSCI 601 at UMass(42)

### View Full Document

## 23

## 0

## 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.

## Similar to Course at UMass

## Popular in Subject

## Reviews for Class Note for CMPSCI 601 at UMass(42)

### 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

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I made $350 in just two days after posting my first study guide."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.