### 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(30)

### View Full Document

## 13

## 0

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

## Similar to Course at UMass

## Popular in Subject

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

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

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

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

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