### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Computation Theory CMPSCI 601

UMass

GPA 3.57

### View Full Document

## 19

## 0

## Popular in Course

## Popular in ComputerScienence

This 177 page Class Notes was uploaded by Roman McCullough on Friday October 30, 2015. The Class Notes belongs to CMPSCI 601 at University of Massachusetts taught by Neil Immerman in Fall. Since its upload, it has received 19 views. For similar materials see /class/232251/cmpsci-601-university-of-massachusetts in ComputerScienence at University of Massachusetts.

## Similar to CMPSCI 601 at UMass

## Popular in ComputerScienence

## Reviews for Computation Theory

### 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: 10/30/15

CMPSCI601 Introduction Lecture 1 Indepth introduction to main models concepts of theory of computation 0 Computability what can be computed in principle 0 Logic how can we express our requirements 0 Complexity what can be computed in practice Concrete Mathematical Problem Formal Models of Computation Finitestate 0 Stacks CFL Turing Machine 0 Logical Formula CMSPSCI 601 Requirements Lecture 1 Texts available at Jeffery Amherst College Store P Christos Papadimitriou Computational C omplex 17 BE Jon Barwise and John Etchemendy Language Proof and Logic Prerequisites Mathematical maturity reason abstractly understand and write proofs CMPSCI 250 needed CMPSCI 3 11 401 helpful Today s material is a good taste of the sort of stuff we will do Work 0 eight problem sets 35 of grade c midterm 30 of grade c nal 35 of grade Cooperation Students should talk to each other and help each other but write up solutions on your own in your own words Sharing or copying a solution could result in failure If a signi cant part of one of your solutions is due to someone else or some thing you ve read then you must acknowledge your source CMSPCI 601 On Reserve in Dubois Library Lecturel Mathematical Sophistication 0 How to Read andDo Proofs Second Edition by Daniel Solow 1990 John Wiley and Sons Review of Regular and ContextFree Languages 0 Hopcroft Motwani and Jeffrey D U11manIntroa uc tion to Automata Theory Languages and Computa tion 2001 Chapters 1 6 0 Lewis and Papadimitriou Elements of the Theory of Computation 1998 Chapters 1 3 0 Sipser Introduction to the Theory of Computation 1997 Chapters 1 2 NP Completeness 0 Garey and Johnson Computers and Intractability 1979 Descriptive Complexity 0 Immerman Descriptive Complexity 1999 3 Syllabus will be up soon on the course web site 0 http www cs umass edu barring08601 There is a pointer there to the Spring 2002 web site and the syllabus there will be close to what we do here Rough guide 0 Formal Languages and Computability 9 lectures 0 Propositional and FirstOrder Logic 7 lectures 0 Complexity Theory 11 lectures CMPSCI 601 Review Of Regular Sets Lecturel De nition An alphabet is a nonempty nite set eg E 01 F abc etc De nition A string over an alphabet E is a nite sequence of zero or more symbols from E The unique string with zero symbols is called 6 The set of all strings over 2 is called 2 De nition A language over 2 is any subset of 2 The decision problem for a language L is to input a string 11 and determine whether 11 E L De nition The set of regular expressions 122 over alphabet E is the smallest set of strings such that l ifa E Ethena E RE 2 e E RE 3 I E RE 4 if e f 6 122 then so are the following a 8 U f b 8 0 f C 6 Examples 0 81 0 E R01 0 82 a U 7 o a U b E Ra 7 0 83 ababa E Ra b 0 Meanings 0 60000304 0i 1 iEN O an2 w 6 ab E 0m0d2 39 ababa w 6 MW 1 120111 E 0m0d2 Recall the meaning of Kleene star for any set A A E ii Ai i0 AouAluAguo eUAUay 3yEAU E 1332n nEN1nEA Meaning of a Regular Expression 1 ifa E 2 then a 6 122 3a a 2 e E RE 6 e 3 7 E RE EUD 7 4 ife f 6 122 then so are e U f e o f 8 178 U f 178 U EU 178 O f 81709 W 1 u E 8771 E Em 175 8 De nition 11 A C 2 is regular iff 38 E REA 8 In other words a set A is regular iff there exists a regular expression that denotes it De nition A deterministic nite automaton DFA is a tuple DQE6SF 0 Q is a nite set of states 0 E is a nite alphabet 0 6 Q X E gt Q is the transition function 0 s E Q is the start state and 0 F C Q is the set of nal or accept states D1 S7q7a7b7617878 61 ltltS7agt78gt7ltlt87bgt7Qgt7ltltQ7agt7Qgt7ltltQ7bgt78gt 9 1 D1 w 6 ab 110112 E 0m0d2 1 ababa De nition A nondeterministic nite automaton NFA is a tuple N QEA3F 0 Q is a nite set of states 0 E is a nite alphabet 0 A Q X E U gt 50Q is the transition function 0 s E Q is the start state and 0 F C Q is the set of nal or accept states MN w 1 SinF 505 2 powersetofS A1AQS Nn 907 39 o 39 7Qn17 07 113157 10 gn1 An ltltQO7Ogt7QOgt7 ltltQO71gt7QO791gt739 39 39 7 ltltQn71gt7Qn1gt 1 01 01 01 01 O O 0 01 You will Show in HW 1 that to accept Nn a DFA would need 2quot1 states Proposition 12 Every NFA N can be translated into an NFA w0 etransitl39ons N39 SJ N N39 Proof GivenN QEAQOF16 ENQ727AI7907FI where A39qar38tq gt81gtt gtr F39 q 1 386396 38 Notation For a DFA D Q E 6 s F let 6q 11 be the state that D will be in after reading string 21 when started in q V0176 E q 5 27 wa E 505 27 w a D E w 6sw E F For an NFA without 6 transitions N Q 215 sF let Aq 11 be the set of states that N can be in after reading string 11 when started in q Ami76 1 Aqwa 2 U Ara TEAqw N E w Asw F7E Proposition 13 For every NFA N with n states there is a DFA D with at most 2 states st D N Proof Let N QEA 1017 By Proposition 12 may assume that N has no 6 transitions Let D we 2 6 90 F 6Sa U Ara TEES F395 Q1SOF7 Claim For all 71 E 2 5 m7 w NMoW By induction on 17111203 5QO 10 AVG076 1w k1 wzua Inductively 6QO7 u N020 u WHQoLW 55qo7u7 a U AUquot a r 5q0u U AUquot a TEAq0u Aq ua ll Therefore D N Theorem 14 Kleene s Th Let A C 2 be any lan guage Then the following are equivalent 1 A Df0r some DFA D 2 A Nf0r some NFA N WO 6 transitions 3 A Nf0r some NFA N 4 A e for some regular expression e 5 A is regular Proof Obvious that l gt 2 gt 3 3 gt 2 by Prop 12 2 gt 1 by Prop 13 subset construction 4 lt gt 5 by def of regular 4 gt 3 We show by induction on the number of symbols in the regular expression e that there is an NFA N with e N ea e S e 0 gt Union C oncatenation LNLN1LN2 LNLN1LN2 N1 Kleene Star LltNgt ltLltN1gt N 3 gt4LetN1nEA1FFf1fr E w j E A22w n0 intermediate state 7 gt k Lg aljeAz aUe1z j k1 k k k k Lij Lij U Lik1Lk1k1 Lk1j ll 5 H LflU ULfT k L kI kI 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 CMPSCI601 NSPACE VS DSPACE Lecture 18 How well can we simulate nondeterministic 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 Tm 0 01 TTnk 707Tnk2 andso TTnn n0WW Corollary 183 Savitch s Theorem For 3n 2 log n DSPACEsn g NSPACEsn C 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 DISTVd1 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 f a1 se for the others Correct guesses can be veri ed and wrong guesses cause the whole procedure to reject GEE REACH e NDISTtnNn 4s 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 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 100p n E K ltgt 1 ltgt 17 Q 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 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 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 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 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 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 CMPSCI601 Summary amp Conclusions Lecture 27 We ve studied the main models and concepts of the the ory of computation 0 Computability what can be computed in principle 0 Logic how can we express our requirements 0 Complexity what can be computed in practice Concrete Mathematical Problem Formal Models of Computation 0 FA g Regular Expression PDA E CFG 0 TM E Recursive Function g Boolean Circuits 0 logical formula CMPSCI 601 Regular Sets Lecture 27 Kleene s Theorem Let A Q 2 be any language Then the following are equivalent 1 A 2 D for some DFA D 2 A 2 N for some NFA N wo 6 transitions 3 A 2 N for some NFA N 4 A 2 e for some regular expression 8 MyhillNerode Theorem The language A is regular iff NA has a nite number of equivalence classes Fur thermore this number of equivalence classes is equal to the number of states in the minimumstate DFA that ac cepts A Pumping Lemma for Regular Sets Let D 2 QZ6 1017 be a DFA Let n 2 Let w E D st 2 n Then Elmyz E 23 st the following all hold 0 acyz 2 w 0 g n 0 gt 0 and 0 Vk 2 0ayquot 39z E D CMPSCI 601 C FL S Lecture 27 Closure Theorem for Context Free Languages Let A B Q 23 be contextfree languages let R Q 23 be a regular language and let h 23 gt I and g I gt 23 be homomorphisms Then the following languages are contextfree l A U B 2 AB 3 A Q R 4 MA 5 9 1A CFL Pumping Lemma Let A be a CFL Then there is a constant 72 depending only on A such that if z E A and 2 n then there exist strings u v w as 3 such that z 2 unwary and 0 I m 2 1 0 11mm 3 n and o for all k E N ruckwacky E A CMPSCI601 Recursive Sets Lecture 27 A partial function is recursive iff it is computed by some TM M LetS Q 01 orS Q N S is a recursive set iff the function X3 is a total recursive function 1 if a E 5 XS 2 0 otherwise 5 is a recursively enumerable set S is re iff the func tion p3 is a partial recursive function lifazES pg 33 otherwise Th Recursive re c0re De ne the primitive recursive functions to be the smallest class of functions that 0 contains the Initial functions C a and 7a n 2 1 2 1 g 239 g n and 0 is closed under Composition and 0 is closed under Primitive Recursion De ne the GO del recursive functions to be the smallest class of functions that 0 contains the Initial functions and 0 is closed under Composition and 0 is closed under Primitive Recursion and 0 is closed under Unbounded Mimimalization Th Kleene COMPn as c y is a primitive recursive predicate Theorem A partial function is recursive iff it is Godel recursive Cantor s Theorem 30N is not countable Proof Suppose it were Let f N13l De ne the diagonal set D n l n f7 b Thus D 2 fk for some k E N kED ltgt mm ltgt MD i Therefore 30N is not countable A n012345678fn 000000000mf0 111111111f1 210010101f2 301001010f3 41000 0000f4 501101001f5 610010000f6 711000000f7 801000000mf8 100011011 D CMPSCI 601 Uses Of Diagonalization Lecture 27 K 2 Theorem Fis not re Hierarchy Theorems Let f be a well behaved function and C one of DSPACE NSPACE DTIME NTIME If gm is suf ciently smaller than f then Cgn is strictly contained in C f L 901 suf ciently smaller than f 71 means limnm Z 0 mum Z 0 c DSPACE NSPACE NTIME c DTIME Hence P y EXPTIME L PSPACE But these are the only separations of classes we know Except at the pr and above level and for REG and CFL Th The busy beaver function is eventually larger than any total recursive function Th Let S Q N TFAE l S is the domain of a partial recursive function 2 S 2 D or S is the range of a total recursive function 3 S is the range of a partial recursive function 4 S 2 Wu some n 2 012 where W m 1 MW 1 CMPSCI 601 Logic Lecture 27 De nitions of Formula Structure and Truth Axioms and Proof Rules Modus Ponens MP From 0 p gt w conclude 2p Proposition Modus Ponens preserves validity Axioms all generalizations of the following O Tautologies on at most three boolean variables la tzt 1c tlzt lAnAtkzt k gtRt1tk gtRt t 2 WW gt W lt t 3 p gt Vacltp a not free in p 4 WW gt I gt WWW gt WWW Proposition Every instance of every axiom is valid FOTHEOREMS 2 go 1 i cp Soundness Theorem If l cp then lch FOTHEOREMS Q FOVALID Completeness Theorem If 90 then l cp FOTHEOREMS Q FOVALID Corollary l FOTHEOREMS 2 FOVALID Compactness Th If every nite subset of F has a model then P has a model Godel s Incompleteness Theorem TheoryN is not re and thus not axiomatizable CMPSCI 601 Complexity Classes Lecture 27 Th For tn 2 71301 2 logn DTIMEtn g NTIMEtn g DSPACEtn DSPACEsn g DTIME205W Savitch s Theorem For 302 2 log n NSPACEsn g ATIMEsn2 g DSPACEsn2 ImmermanSzelepcs nyi Theorem For 302 2 log n NSPACEsn 2 coNSPACEsn CMPSCI 601 Reductions Lecture 27 Theorem Let C be one of the following complex ity classes L NL P NP coNP PSPACE EXPTIME PrimitiveRecursive RECURSIVE re core Suppose A g B IfBEC Then AEC All these complexity classes are closed under reduc tions Lower Bounds If A is hard then B is hard Upper Bounds If B is easy then A is easy CMPSCI 601 Complete Problems Lecture 27 Complete for NL REACH EMPTYDFA EMPTY NFA 2SAT Complete for P CVP MCVP EMPTYCFL Hom SAT REACHa Complete for NP TSP SAT 3SAT 3COLOR CLIQUE Subset Sum Knapsack Complete for PSPACE QSAT GEOGRAPHY SUCCINT REACH REGEXPE Complete for re K HALT A0317 FOVALID Complete for core K ZY CFL EMPTY FOSAT CMPSCI 601 Descriptive Complexity Lecture 27 Theorem re 2 FOEKN c0 re 2 FOWN PH 2 SO NP 2 803 P 2 SOSHorn AC0 2 CRAM1 LH 2 F0 One can understand the complexity of a problem as the richness of a logical language that is needed to describe the problem CMPSCI 601 Alternation Lecture 27 Theorem For 301 2 log n and for tn 2 n kOglATIMEtnk 1DSPACEtnk ASPACEsn I DTIMEWW 1 Corollary In particular ASPACE10gn 2 P ATIMEn0lt1gt PSPACE ASPACEn0lt1gt EXPTIME CMPSCI 601 Circuit Complexity Lecture 27 depth 2 parallel time width 2 hardware number of gates 2 computational work 2 sequential time Theorem For alli CRAMlognquot39 2 ACquot AC0 g ThC0 g NC1 g L g NL g sAC1 g AC1 g ThC1 g NC2 g sAC2 g g g g g ACZ39 g ThCZ39 g NCM g sAC g g g g 2 NC 2 NC 2 NC 2 NC 2 NC g P g NP AlternationCircuit Theorem Logspace ATM s with Ouagi n time give NCl 239 2 1 0logi n alternations give ACquot 239 2 1 Alternating TM s are one good way to design uniform families of circuits We used this method to prove CFL g sACl Firstorder logic gives us another way to design uniform families of circuits We ve used this to construct AC0 circuits by showing a problem to be in F0 We need uniformity de nitions on our circuit classes to relate them to ordinary classes For example polysize circuit families compute languages in P only if they are at least Puniform Theorem PRIME and Factoring are in NP 0 coNP PRIME is now in P as well Theorem SolovayStrassen Miller PRIME E BPP Fact REACHu E BPL Interactive Proofs NP P gtMAAM AMpoly IP PSPACE BPN P BPP Fact PCPlog n 1 NP CMPSCI 601 Optimization Lecture 27 A is an optimization problem iff For each instance as F is the set of feasible solutions Each 3 E has a cost 03 6 Zer For minimization problems OPTa 2 Sgg 03 For maximization problems OPTa 2 813216 03 Let M be an algorithm st on any instance as M is an eapproximation algorithm iff for all as 16M56 0PT561 6 maxOPTa Clizlue TSP INAPPROX exists P appmx algfar n0 8 lt I VerteXCover MAX SAT ATSP APPROX same but nat all 8lt I PT As ETSP all 8lt I Kn apsac poly in n 18 20 FOVU D c0 re Arithmetic Hierarchy F0 N Recursive Primitive Recursive re re complete F0 EN co NP EXPTIME complete c0NP PSPACE SOV PolynomialTime Hierarchy SO NP 1 c0NP NP SOEI NP complete quottruly feasibl en SOHorn NC NC2 logCFL NSPACElog n SACl DSPACElog n Regular LogarithmicTime Hierarchy 21 CMPSCI 601 Where s the Catch Lecture 27 Why are the following so hard to prove P 7 NP P PSPACE ThC0 7 NP BPPP We do know a lot about computation Reductions and complete problems are a key tool So is the equivalence of apparently different models and methods Yet much remains unknown 22 CMPSCI 601 Recall From Last Time Lecture 24 Parallel Computation Many computations at once we measure parallel time and amount of hardware Models time measure hardware measure 0 Parallel RAM number of steps number of processors 0 Alternating TM alternations 23 c Boolean Circuits depth size Uniformity The ninput circuit in the family must be easily FL or FFO computable from input 1 Theorem P equals uniform PSIZE NC Hierarchy Classes of programs with fast log 7001 time parallel algorithms that use reasonable 7101 hard ware De nition 241 The NC Hierarchy Let tn be a poly nomially bounded function and let S Q 01 Then S is in the circuit complexity class NCtnl AC tn ThCtn respectively iff there exists a uniform family of circuits Cl 02 with the following properties 1 For allw E 0 l w E S 42gt Clw1wl 2 The depth of On is 3 10 3 7201 4 The gates of On consist of NC AC ThC bounded fanin unbounded fanin unbounded fanin and or gates and or gates threshold gates ismExo x Fori01 NCquot NC log ACquot 2 AClog ThCl ThClogn ll 2 Z 6 NC ONCl OACl find We will see that the following inclusions hold AC0 g Thc0 g NClQLQNL g AC1 AC1 g ThC1 g NC2 g AC2 AC2 g ThC2 g NC3 g AC3 3 Q s Q Q s lAd LllThCl ENC NC Overall NC consists of those problems that can be solved in polylog parallel time on a parallel computer withpoly nomially much hardware The question of whether P 2 NC is the second most important open question in com plexity theory after the P 2 NP question You wouldn t think that every problem in P can be sped up to polylog time by parallel processing Some prob lems appear to be inherently sequential If we prove that a problem is Pcomplete we know that it is not in NC unless P 2 NC Theorem CVP MCVP and HORNSAT are all P complete Proof CVP by analysis of P 2 uniform PSIZE proof The other two by reduction from CVP Proposition 242 Every regular language is in NC 1 There are several different ways to prove this The basic idea is to use divideandconquer to determine the behav ior of a DFA on a string One way to look at it is that we know the behavior of the DFA on each letter as a function from the state set to itself We need to compose together these n different behaviors to get the benavior of the DFA on the whole string We can compose two functions from an O1size set to itself in NC0 01 size and depth A binary tree of these composition operations gets the whole behavior in NC Another way to prove it is to draw a levelled graph of length n and width 01 with a node for each state of the DFA at each time and and edge for the transition that the DFA will make at that time looking at that letter of at We now have a REACH problem on a constantwidth graph and we can adapt the Savitch argument to do this in NC This Savitch argument may be easier to see in the follow ing very similar result Theorem 243 Every regular language is m ATIMElog Proof We are given the input string 11 of length n and a DFA D for the language White initially names the nal state in which D nishes on input 11 In general White has a claim of the form 1239 339 7 meaning if D starts in state q and reads the string w 11 it ends in state 7 White advances her claim by naming the state of D in the middle of the current string Black challenges either the rst half or second half of White s claimed behavior When the claim is about one letter of w it can be tested against the table of D and that letter from the input tape There are log n rounds and in each White names a state 01 bits and Black names a bit A Actually with a suitable uniformity condition Theorem Ruzzo NC1 ATIMElog n We ll prove this later in this lecture though Without the uniformity details Theorem 244 BarringtonImmermanStraubing F0 2 AC0 Proof Sketch of one direction with some uniformity details skipped 99 3Vy3zMwayz Proposition 245 F0ri01 NCZ39 g ACZ39 g ThCi g NCH1 Proof All inclusions but ThCi g NCML are clear MAJ w 6 01 1 whas more than 1w12 1 s e ThC0 Lemma 246 MAJ 6 NC1 and the same for any other threshold gate The obvious way to try to build an NCL circuit for maj or ity is to add the n input bits Via a full binary tree of height log n The problem with this is that while the sums being added have more and more bits we must still add them in constant depth each It s actually provabe impossible to add two numbers of more than constant length in constant depth if we use standard binary notation and gates of fanin two This is because the hi ghestorder output bit might depend on any of the input bits and so needs to be connected to all of them Via wires 0 was QQQg gf ogogogoogbgg i XXXXXX 12 3456X7X8 pgi z A solution to this problem is Via redundant arithmetic notation Consider a representation of natural numbers in binary except that digits 0123 may be used For example 3213 and 3221 are different representations of the decimal number 37 in this redundant notation 3213 323222121320 37 3221 323222221120 37 Lemma 247 Adding two 72 bit numbers with input and output in redundant notation can be done with an NC0 circuit ie with constant depth and constant fanin Example carries 3 2 2 3 3213 3213 32210 This is doable in NC0 because the carry from column 239 can be computed by looking only at columns 239 and 239 1 Details will be on HW8 Translating from redundant notation back to binary which must be done only once at the end is just an addition problem This is rstorder and thus AC0 and thus NC A in L and Lecture 24 CMPSCI 601 Theorem 248 Borodin NCL g L Proof Use a recursive evaluation of the circuit boolean eval a method in the Gate class if type OR return lefteval righteval if type AND return lefteval ampamp righteval if type INPUT return inputValue We must save 01 bits each time we recurse and our recursion depth is the depth of the circuit 010g Thus 4 we use Olog n space Theorem 249 Savitch NL g AC1 Proof Express the Savitch middle rst search algorithm for REACH as a circuit For every two nodes u and v and every number d up to log n have a gate Guv d that will evaluate to true iff there is a path from u to v of length at most 2d Then Gu 1 CH1 is the OR over all nodes 11 ofGu w d AND Gw v d Gu v 0 is the input bit Eu v OR ed with u 2 11 There are only polynomially many gates and our depth using unbounded fanin is clearly Olog A Note that this circuit uses unbounded fanin only for OR gates so it is in a subclass of ACL called sACl By a proof similar to ImmermanSzelepcsenyi it can be shown that SACl is closed under complement it can be de ned either with bigORsonly or bigANDsonly l CMPSCI601 The AlternationCircuit Theorem Lecture 24 We know that ASPACElog n 2 P and we have de ned subclasses of P in terms of circuits with limited depth It turns out that these same subclasses can also be de ned in terms of alternating Turing machines We de ne sub classes of ASPACElog n in terms of limited time and limited number of alternations Theorem 2410 Ruzzo For allz39 2 l 0 NC equals the languages OfATM s with space Olog n and time OlogZ 0 ACquot equals the languages OfATM s with space Olog n and Olog2 n alternations Proof This is a sketch omitting many uniformity de tails For example the exact uniformity de nition used for NCL is a messy one designed speci cally to make NC1 equal ATIMElog 72 First consider simulating ATM s by circuits If we make a gate for each of the 7101 con gurations we can con nect these gates into a circuit in an obvious way The type of the gate for con guration 0 is AND if c is a Black move universal con guration and OR if it is White move existential A terminal con guration becomes an constant gate The children of c are the two con gura tions that the ATM can move to from c The output gate is the start con guration But we have a problem in that the children of a gate de pend on the input and we can t let the structure of the circuit depend on the input only on its size However following Problem 5 on Spring 2003 s HW7 we can assume that the ATM is a one00k machine that only queries its input tape once at the end of the computation To be complete we would need to prove a lemma that we can enforce the onelook restriction preserving time or preserving alternations I may or may not put this on HW8 What is the depth of the resulting circuit It is equal to the running time of the ATM assuming we make the cir cuit have fanin two This shows the NC part of this half of the theorem that the ATM with 010gn space and Ologi n time can be simulated in NCl Note that the circuit to simulate the ATM will be very uniform If we take the circuit we have constructed and collapse it to an unbounded fanin circuit by merging ANDs with ANDs or ORs with ORs on consecutive levels then our depth is reduced from the running time to the number of alternations Each phase of allAND or allOR gates be comes a single level of the new circuit There are some details to check to make sure that this construction is suf ciently uniform But we only care in the case of ACL and above and in ACL we can test REACH and thus de cide whether one gate can be reached from another by a path of all AND or all OR gates This with some details missing concludes the simula tion of ATM s by circuits We now need to show the other half of the theorem that we can simulate a circuit with an ATM But we ve really already done this in de ning the Circuit Game to solve MCVP in ASPACElog Why can we assume mono tone circuits See HW8 If the input circuit is fanin two and depth Ologi n an NCi circuit the exact same Circuit Game will be com pleted in Ologi n moves of the game But can we imple ment a move of the game in 01 time on the machine We can have the players make their choices by writing down a bit for each move But how do we know whose move it is and where we are in the circuit If we wrote down the new gate number each time we would neces sarily take Ologi1n time in all as each gate number has Olog n bits The trick is to amortize the cost of writing down the gate number by doing it only every log n moves In between the players operate by looking at the last gate number recorded and the sequence of moves since then We allow challenges to any claims about whose move it is or what the new gate number should be so we need the circuit to be uniform enough that we can decide these challenges If the input circuit has unbounded fanin the player in the Circuit Game picking a child must write down its entire gate number and then claim subject to challenge that this gate is really a child Now the moves of the game take time Olog n each but each move is only a single alternation so the number of alternations is bounded by the depth of the circuit This completes the proof of the theorem A l CMPSCI601 Alternation and CFL S Lecture 24 We ll conclude our discussion of parallel complexity by showing where another one of our existing classes the contextfree languages ts into the NC hierarchy Theorem 2411 Ruzzo If G is any contextfree gram mar 30 6 sACl Proof Using the AltemationCircuit theorem we ll prove this by designing an ATM game for G that has the fol lowing properties White wins the game on input 71 iff w 6 30 0 the game uses Olog n space 0 the number of alternations is Olog n and 0 all Black s alternation phases consist of a single bit move When we covert this game to a circuit the last clause ensures that all the AND gates have fanin two so we are in sACl Though our best upper bound for REACH is also sACl it is believed that REACH is not complete for sAC39lL while there are CFL s that are complete for it 19 Let s assume that G is in Chomsky normal form only rules of the form A gt BC A gt a or S gt e We have an input string 11 and White claims there is a way to derive S gt 11 using the rules of G Black as usual disputes this White advances her claim by naming a node in the middle of the parse tree and saying what it does Speci cally for some 239 j and A she says 5 gt 1111 wiAwj 21 and A gt w 21 Black picks one of these two claims to challenge If White is telling the truth about the orginal claim she can get two true claims by telling the truth But if she is lying one of her two subsidiary claims must be a lie We continue the process until we have a claim about a single input letter such as A gt 11 which can be veri ed by looking up the input letter and checking the rules of G 20 This is a valid ATM game that decides whether 11 6 30 but it does not yet meet our speci cation There are two problems 0 The game could last as long as n 1 moves rather than the Olog n we need and 0 The subclaim under dispute might not be speci able in space Olog n as it has the form A gt wil 215ng quwis We need Olog n bits to record each scar in the string 21 We solve the rst problem by setting a fair time limit on White If she has not reduced the claim to one letter in Olog n moves she loses But why is this fair On her move she is dividing the parse tree of 11 into two pieces by cutting an edge Lemma LiptonTarjan Any binary tree can be cut on some edge into two pieces each at most 23 the original size Proof on Spring 2003 HW8 solutions on my web site So since White is so smart she can choose her division to leave smaller subtrees and after Olog n moves she can reduce the subtree to one node 22 To solve the second problem we force White to make sure that the current claim is about a tree with at most three scars giving her Olog n more moves to spend on this goal Lemma Let T be any rooted binary tree and let a b and c be any three nodes none of which is an ancestor of another Then there exists a node d that is an ancestor of exactly two of a b and 0 Proof on Spring 2003 HW8 with posted solutions Now if White is faced with a tree with scars at a b and c we force her to nd some d and divide the tree there This may not shrink the tree under dispute very much but it makes sure that on the next move the two subclaims have only two scars each White still wins the revised game iff she should and the revised game now ts all the speci cations A 23 mm Arlthmetlc H1erarchy W c0re Recursive 139 e re complete Primitive Recursive EXPTIME PSPACE PolynomialTime Hierarchy NP co NP complete c0NP NP 1 c0NP NP complete quottruly feasiblequot NC NC 2 logCFL SAC NSPACE log n DSPACE log n 3 Regular LogarithmicTime Hierarchy 24 CMPSCI 601 Recall Circuit Complexity Lecture 25 depth parallel time width hardware number of gates computational work sequential time Theorem For alli CRAMlogni ACi AC0 g Thc0 g NC1 g L g NL g sAC1 g AC1 g ThC1 g NC2 g sAC2 g gNCi OACi orhci NC g P NCtn ParallelTimetn on real hardware ACtn CRAMtn ThCtn ParallelTimetn on wetware sAC i ACi but gates bounded AlternationCircuit Theorem Forz 2 1 0 NCi equals ATM s with Olog n space Ologi n time 0 ACi equals ATM s with Olog n space Ologi n al ternations Proof Outline Simulate ATM s by circuits by mak ing a node for each con guration Simulate circuits by ATM s using the Circuit Game Note that the AC0 case of the statement of this theorem is false AC0 is not equal to ATM s with 010gn space and 01 alternations that s the logspace hierarchy On HW7 you used ImmermanSzelepcsenyi to prove that this hierarchy is just NL What AC0 actually equals is the logtime hierarchy ATM s with Olog n time and 01 alternations This is also equal to F0 given the suitable precise de nitions sAC Circuit or and or and Of unbounded 0r s bounded and s Fact 251 sAC1 LOGCFL A 1 3aCFLBAg B l CMPSCI601 Alternation and CFL S Lecture 25 We ll conclude our discussion of parallel complexity by showing where another one of our existing classes the contextfree languages ts into the NC hierarchy Theorem 252 Ruzzo If G is any contextfree grammar G E sACl Proof Using the AltemationCircuit theorem we ll prove this by designing an ATM game for G that has the fol lowing properties White wins the game on input 71 iff w 6 30 0 the game uses Olog n space 0 the number of alternations is Olog n and 0 all Black s alternation phases consist of a single bit move When we covert this game to a circuit the last clause ensures that all the AND gates have fanin two so we are in sACl Though our best upper bound for REACH is also sACl it is believed that REACH is not complete for sAC39lL while there are CFL s that are complete for it 4 Let s assume that G is in Chomsky normal form only rules of the form A gt BC A gt a or S gt e We have an input string 11 and White claims there is a way to derive S gt 11 using the rules of G Black as usual disputes this White advances her claim by naming a node in the middle of the parse tree and saying what it does Speci cally for some 239 j and A she says 5 gt 1111 wiAw l 2127 and A gt w wj Black picks one of these two claims to challenge If White is telling the truth about the orginal claim she can get two true claims by telling the truth But if she is lying one of her two subsidiary claims must be a lie We continue the process until we have a claim about a single input letter such as A gt 11 which can be veri ed by looking up the input letter and checking the rules of G This is a valid ATM game that decides whether 11 6 30 but it does not yet meet our speci cation There are two problems 0 The game could last as long as n 1 moves rather than the Olog n we need and 0 The subclaim under dispute might not be speci able in space Olog n as it has the form A gt wil wingig 11114021115 We need Olog n bits to record each scar in the string We solve the rst problem by setting a fair time limit on White If she has not reduced the claim to one letter in Olog n moves she loses But why is this fair On her move she is dividing the parse tree of 11 into two pieces by cutting an edge Lemma LiptonTarjan Any binary tree can be cut on some edge into two pieces each at most 23 the original size Proof on Spring 2003 HW8 solutions on my web site So since White is so smart she can choose her division to leave smaller subtrees and after Olog n moves she can reduce the subtree to one node To solve the second problem we force White to make sure that the current claim is about a tree with at most three scars giving her Olog n more moves to spend on this goal Lemma Let T be any rooted binary tree and let a b and c be any three nodes none of which is an ancestor of another Then there exists a node d that is an ancestor of exactly two of a b and 0 Proof on Spring 2003 HW8 with posted solutions Now if White is faced with a tree with scars at a b and c we force her to nd some d and divide the tree there This may not shrink the tree under dispute very much but it makes sure that on the next move the two subclaims have only two scars each White still wins the revised game iff she should and the revised game now ts all the speci cations A CMPSCI601 O1Depth Threshold Circuits Lecture 25 What we call ThCi here is often called TCi elsewhere ThC0 is the set of languages solvable by threshold cirucits of poly size and constant depth We proved ThC0 g NCL by showing how to add n nbit numbers in NCl using redundant binary notation base two with digits 0123 This has the effect that there are now many different funny ways to write the same number The idea is that we can add two funny numbers in NC so we can add n of them in NCL and then nally convert the funny result to stan dard binary in AC0 g NCl On HW8 you ll provide some of the details of the con struction to add two funny numbers in NC Some problems in TC 0 Addition of two 72bit numbers is in F0 AC0 the carry lookahead adder 0 Addition of n nbit numbers is in ThC0 but not in AC0 by redundant notation 0 Multiplication of two 71bit numbers is in ThC0 but not in AC0 0 Sorting of n nbit numbers is in ThCO Compare each of the 722 pairs in parallel then count up the Wins for each item to get its place 0 Division and iterated multiplication of two 71bit num bers to n bits of accuracy is in polynomialtime uni form ThCO BCH86 Reif87 using Chinese re mainder notation 0 Division is in rstorder uniform ThCO Bill HesseOl HAB02 Lower Bounds Against AC0 We just asserted that the iterated addition and multiplica tion problems are not in AC0 How could one prove such a thing The argument is called a size lower bound for constant depth unbounded fanin circuits Lower bounds often call for detailed combinatorial arguments In this case FurstSaxeSiper yes Sipser the author and Sipser my PhD advisor and Ajtai proved in the early 1980 s that for any d depthd unbounded fanin circuits need super polynomial size to decide the language PARITY w 21 has an odd number of ones It is not hard to show that PARITY circuitreduces to iter ated addition and to multiplication as de ned in HW7 By the downward closure of AC then neither of these problems can be in AC The key to the lower bound proof which we won t cover in this course is randomized restriction They show that by setting all but bits of the input randomly to O or 1 you can turn a depthd circuit computing PARITY of n variables to a slightly larger depthd l circuit comput ing PARITY of the remaining variables Repeating this process leads to a contradiction unless the original circuit was superpolynomial size Later Yao and Hastad showed that a depthd PARITY circuit must have exponential size In 1986 Smolensky considered circuits that along with AND and OR gates also have gates counting modulo some constant m He showed that with a prime modulus p you cannot count the ones in the input modulo any number that is not a power of p Embarassingly it remains open to show any meaning ful size lower bounds on constantdepth circuits of AND OR and modm gates where m is 6 or any product of two or more primes Such circuits might for all we can prove be able to solve NPcomplete problems l CMPSCI 601 PSPAC E Lecture 25 PSPACE DSPACEn0lt1gt NSPACEn0lt1gt 0 PSPACE consists the problems we could solve with a feasible amount of hardware but with limit on com putation time 0 PSPACE is a large and very robust complexity class 0 With polynomially many bits of memory we can search any implicitlyde ned graph of exponential size This leads to complete problems such as reachability on exponentiallylarge graphs 0 We can search the game tree of any board game whose con gurations are describable with polynomiallymany bits This leads to complete problems concerning win ning strategies CMPSCI601 PSPACEComplete Problems Lecture 25 Recall that part of Lecture 23 s Altemation Theorem says PSPACE ATIMEn0lt1gt Recall Q SAT the quanti ed satis ability problem which is the set of true quanti ed boolean formulas Proposition 253 QSAT is PSPACEcomplete Proof In Lecture 23 we proved that QSAT is in ATIME n and hence in ATIMEnO1 This is because the two players can guess the quanti ed boolean variables and the referee can then evaluate the formula with these val ues It remains to show that QSAT is hard for ATIME Let M be an arbitrary ATIME machine Let M write down its nk alternating choices 162 an and then deterrninistically evaluate its input using the choice vector 6 Let the corresponding DTIMEW machine be D For all inputs w l 42gt 301V02 ancnkDcw 1 Applying the tableau construction from the proof of the Fagin or CookLevin theorems to D we see that there is a reduction f from D to SAT so that Dcw 1 ltgt ow 6 SAT Let the new boolean variables in f c 11 be d1 dam M accepts w iff 301V02 ancnk3d1 dtnfcw E QSAT Q GEOGRAPHY is a game with players E and A played on a directed graph with start node 3 l E chooses a vertex 111 with an edge from s 2 A chooses v2 having an edge from 111 3 E chooses v3 have an edge from m And so on No vertex may be chosen twice Whoever moves last Wins In the original version of the game the vertices consist of all known place names and there is an edge from u to 1 iff the last letter of u s name is the rst letter of 11 s as in this graph Texas Selma Africa Transylvania Proposition 254 Figuring out which player has a win ning strategy in a given position of GEOGRAPHY is PSPACEcomplete Proof GEOGRAPHY E PSPACE search the polynomial depth game tree Other Half QSAT g GEOGRAPHY Given a quanti ed boolean formula 0 there is a general construction to build a graph G90 such that player E wins the game on G90 iff the formula is true We rst set up ver tices so that player E chooses a value for each existential variable and player A choose one for each universal vari ables Then we make vertices for each graph so that A s last move picks a clause and E can then move iff that clause is satis ed by some literal set to true by one of the players Here is the graph G90 where p z 3aVb3ca v b 13 v c b v 5 De nition 255 A succinct representation of a graph is 0010 V E s t where C is a boolean circuit with 272 inputs and V w wEO1quot E 711711 Cww l SUCCINCT REACH n C st 1 Gm C e REACH Q Proposition 256 SUCCINCT REACH is PSPACEcomplete Proof This was assigned as a problem on Spring 2003 s Homework 8 and is solved on the web pages for that version of the course A Suitably generalized to n by n versions G0 and Chess are also both PSPACEcomplete In general an n by n game where the playing board can change is going to be PSPACEcomplete because it can simulate alternating polytime A game where 01 pieces move around on a board is going to be Pcomplete because it can simulate alternating log space CMPSCI 601 Recall From Last Time Lecture 23 Parallel Computation Many computations at once we measure parallel time and amount of hardware Models time measure hardware measure 0 Parallel RAM number of steps number of processors 0 Alternating TM alternations 23 c Boolean Circuits depth size Uniformity The ninput circuit in the family must be easily FL FFO computable from input 1 Theorem P is uniform PSIZE NC Hierarchy Classes of programs with fast log 7001 time parallel algorithms that use reasonable 7101 hard ware De nition 231 The NC Hierarchy Let tn be a poly nomially bounded function and let S Q 01 Then S is in the circuit complexity class NCtnl AC tn ThCtn respectively iff there exists a uniform family of circuits Cl 02 with the following properties 1 For allw E 0 l w E S 42gt Clw1wl 2 The depth of On is 3 10 3 7201 4 The gates of On consist of NC AC ThC bounded fanin unbounded fanin unbounded fanin and or gates and or gates threshold gates ismExo x Fori01 NCquot NC log ACquot 2 AClog ThCl ThClogn ll 2 Z 6 NC ONCl OACl find We will see that the following inclusions hold AC0 g Thc0 g NClQLQNL g AC1 AC1 g ThC1 g NC2 g AC2 AC2 g ThC2 g NC3 g AC3 3 Q s Q Q s lAd LllThCl ENC NC Overall NC consists of those problems that can be solved in polylog parallel time on a parallel computer withpoly nomially much hardware The question of whether P 2 NC is the second most important open question in com plexity theory after the P 2 NP question You wouldn t think that every problem in P can be sped up to polylog time by parallel processing Some prob lems appear to be inherently sequential If we prove that a problem is Pcomplete we know that it is not in NC unless P 2 NC Theorem CVP MCVP and HORNSAT are all P complete Proposition 232 Every regular language is in NC 1 There are several proofs of this the basic idea is to use divideandconquer to determine the behavior of a DFA on a string This can be rephrased as composing together the DFA behaviors on each letter using a binary tree of composition operators or as solving a reachability prob lem on a constantWidth graph by Savitch By a very similar argument you can show that every reg ular language is in ATIMElog Actually With a suit able uniformity condition Theorem Ruzzo NC1 ATIMElog n We ll prove this later in this lecture though Without the uniformity details Theorem 233 BarringtonImmermanStraubing F0 2 AC0 Proof Sketch of one direction with some uniformity details skipped 99 3Vy3zMwayz Proposition 234 F0ri01 NCZ39 g ACZ39 g ThCi g NCH1 Proof All inclusions but ThCi g NCML are clear MAJ w 6 01 1 whas more than 1w12 1 s e ThC0 Lemma 235 MAJ E NCL and the same for any other threshold gate The obvious way to try to build an NCL circuit for maj or ity is to add the n input bits Via a full binary tree of height log n The problem with this is that while the sums being added have more and more bits we must still add them in constant depth 0 0 o b aaaaaaaal 12345678 12 A solution to this problem is Via ambiguous arithmetic notation Consider a representation of natural numbers in binary except that digits 0123 may be used For example 3213 and 3221 are different representations of the decimal number 37 in this ambiguous notation 3213 323222121320 37 3221 323222221120 37 l l Lemma 236 Adding two 72 bit numbers in ambiguous notation can be done via an NC0 circuit ie with bounded depth and bounded fanin Example carries 3 2 2 3 3213 3213 32210 This is doable in NC0 because the carry from column 239 can be computed by looking only at columns 239 and 239 1 Translating from ambiguous notation back to binary which must be done only once at the end is just an addition problem This is rstorder and thus AC0 and thus NC A in L and Lecture 23 CMPSCI 601 Theorem 237 Borodin NC1 g L Proof Use a recursive evaluation of the circuit boolean eval a method in the Gate class if type OR return evalleft if type AND return evalleft evalright ampamp evalright if type INPUT return inputValue We must save 01 bits each time we recurse and our recursion depth is the depth of the circuit 010g Thus 4 we use Olog n space Theorem 238 Savitch NL g AC1 Proof Express the Savitch middle rst search algorithm for REACH as a circuit For every two nodes u and v and every number d up to log n have a gate Guv d that will evaluate to true iff there is a path from u to v of length at most 2d Then Gu v d1 is the OR over all nodes 11 ofGu w d AND Gw v d Gu v 0 is the input bit Eu v OR ed with u 2 11 There are only polynomially many gates and our depth using unbounded fanin is clearly Olog A Note that this circuit uses unbounded fanin only for OR gates so it is in a subclass of ACL called sACl By a proof similar to ImmermanSzelepcsenyi it can be shown that SACl is closed under complement it can be de ned with bigORsonly or bigANDsonly l CMPSCI601 The AlternationCircuit Theorem Lecture 23 We know that ASPACElog n 2 P and we have de ned subclasses of P in terms of circuits with limited depth It turns out that these same subclasses can also be de ned in terms of alternating Turing machines We de ne sub classes of ASPACElog n in terms of limited time and limited number of alternations Theorem 239 Ruzzo For all i 2 l 0 NC equals the languages OfATM s with space Olog n and time OlogZ 0 ACquot equals the languages OfATM s with space Olog n and Olog2 n alternations Proof This is a sketch omitting many uniformity de tails For example the exact uniformity de nition used for NCL is a messy one designed speci cally to make NC1 equal ATIMElog 72 First consider simulating ATM s by circuits If we make a gate for each of the 7101 con gurations we can con nect these gates into a circuit in an obvious way The type of the gate for con guration 0 is AND if c is a Black move universal con guration and OR if it is White move existential A terminal con guration becomes an constant gate The children of c are the two con gura tions that the ATM can move to from c The output gate is the start con guration But we have a problem in that the children of a gate de pend on the input and we can t let the structure of the circuit depend on the input only on its size However following Problem 5 on HW7 we can assume that the ATM is a one00k machine To be complete we would need to prove a lemma that we can enforce the onelook restriction preserving time or preserving alternations What is the depth of the resulting circuit It is equal to the running time of the ATM assuming we make the cir cuit have fanin two This shows the NC part of this half of the theorem If we take the circuit we have constructed and collapse it to an unbounded fanin circuit by merging ANDs with ANDs or ORs with ORs on consecutive levels then our depth is reduced from the running time to the number of alternations Each phase of allAND or allOR gates be comes a single level of the new circuit There are some details to check to make sure that this construction is suf ciently uniform But we only care in the case of ACL and above and in ACL we can test REACH and thus de cide whether one gate can be reached from another by a path of all AND or all OR gates This with some details missing concludes the simula tion of ATM s by circuits We now need to show the other half of the theorem that we can simulate a circuit with an ATM But we ve really already done this in de ning the Circuit Game to solve MCVP in ASPACE log If the input circuit is fanin two and depth Ologquot n an NCi circuit the exact same Circuit Game will be com pleted in Ologi n moves of the game But can we imple ment a move of the game in 01 time on the machine We can have the players make their choices by writing down a bit for each move But how do we know whose move it is and where we are in the circuit If we wrote down the new gate number each time we would neces sarily take Ologi1n time in all as each gate number has Olog n bits The trick is to amortize the cost of writing down the gate number by doing it only every log n moves In between the players operate by looking at the last gate number recorded and the sequence of moves since then We allow challenges to any claims about whose move it is or what the new gate number should be so we need the circuit to be uniform enough that we can decide these challenges If the input circuit has unbounded fanin the player in the Circuit Game picking a child must write down its entire gate number and then claim subject to challenge that this gate is really a child Now the moves of the game take time Olog n each but each move is only a single alternation so the number of alternations is bounded by the depth of the circuit This completes the proof of the theorem Q l CMPSCI601 Alternation and CFL S Lecture 23 We ll conclude the discussion of parallel complexity by showing where another one of our existing classes the contextfree languages t into the NC hierarchy Theorem 2310 Ruzzo If G is any contextfree gram mar 30 6 sACl Proof Using the AltemationCircuit theorem we ll prove this by designing an ATM game for G that has the fol lowing properties White wins the game on input 71 iff w 6 30 0 the game uses Olog n space 0 the number of alternations is Olog n and 0 all Black s alternation phases consist of a single bit move When we covert this game to a circuit the last clause ensures that all the AND gates have fanin two so we are in sACl Though our best upper bound for REACH is also sACl it is believed that REACH is not complete for sAC39lL while there are CFL s that are complete for it 18 Let s assume G is in Chomsky normal form We have an input string 11 and White claims there is a way to derive S gt 11 using the rules of G Black as usual disputes this White advances her claim by naming a node in the middle of the parse tree and saying what it does Speci cally for some 239 j and A she says 5 gt 1111 wz AUIj1 21 and A gt w 21 Black picks one of these two claims to challenge If White is telling the truth about the orginal claim she can get two true claims by telling the truth But if she is lying one of her two subsidiary claims must be a lie We continue the process until we have a claim about a single input letter such as A gt 11 which can be veri ed by looking up the input letter and checking the rules of G This is a valid ATM game that decides whether 11 6 30 but it does not yet meet our speci cation There are two problems 0 The game could last as long as n 1 moves rather than the Olog n we need and 0 The subclaim under dispute might not be speci able in space Olog n as it has the form A gt 2111 wingis mac1115 We need Olog n bits to record each scar in the string We solve the rst problem by setting a fair time limit on White If she has not reduced the claim to one letter in Olog n moves she loses But why is this fair On her move she is dividing the parse tree of 11 into two pieces by cutting an edge Lemma LiptonTarjan Any binary tree can be cut on some edge into two pieces each at most 23 the original size Proof on HW8 So since White is so smart she can choose her division to leave smaller subtrees and after Olog n moves she can reduce the subtree to one node 20 To solve the second problem we force White to make sure that the current claim is about a tree with at most three scars giving her Olog n more moves to spend on this goal Lemma Let T be any rooted binary tree and let a b and c be any three nodes none of which is an ancestor of another Then there exists a node d that is an ancestor of exactly two of a b and 0 Proof on HW8 Now if White is faced with a tree with scars at a b and c we force her to nd some d and divide the tree there This may not shrink the tree under dispute very much but it makes sure that on the next move the two subclaims have only two scars each White still wins the revised game iff she should and the revised game now ts all the speci cations Q 21 mm Arlthmetlc H1erarchy W c0re Recursive 139 e re complete Primitive Recursive EXPTIME PSPACE PolynomialTime Hierarchy NP co NP complete c0NP NP 1 c0NP NP complete quottruly feasiblequot NC NC 2 logCFL SAC NSPACE log n DSPACE log n 3 Regular LogarithmicTime Hierarchy 22 CMPSCI 601 Recall From Last Time Lecture 9 Def DTIME NTIME DSPACE measured on Multi tape Turing Machines Th DTIMEtn g RAMTIMEtn g DTIMEtn3 L E DSPACE10gn P DTIMEn0lt1gt EJCDTIMEW i1 NP 2 NTIMEn0lt1gt EJCNTIMEW 2 1 PSPACE DSPACEn0lt1gt 061DSPACEni 2 Th For tn 2 n 2 log n DTIMEtn g NTIMEtn g DSPACEtn DSPACEsn g DTIME20ltSlt gtgt Cor L 0 w W NP g PSPACE l CMPSCI601 NTIME and NP Lecture9 NTIME probs accepted by NTMs in time Otn NP NTIMEn0lt1gt cillNTIMEW 6 Theorem 91 For any function DTIMEtn g NTIMEtn g DSPACEtn Proof The rst inclusion is obvious For the second note that in space Otn we can simulate all computa tions of length Otn so we will nd the shortest ac cepting one if it exists A Recall DSPACEtn g DTIME20lttltngtgt Corollary 92 L g P g NP g PSPACE So we can simulate NTM s by DTM s at the cost of an exponential increase in the running time It may be pos sible to improve this simulation though no essentially better one is known If the cost could be reduced to poly nomial we would have that P 2 NP There is probably such a quantitative difference between the power of NTM s and DTM s But note that qualita tively there is no difference If A is the language of some NTM N it must also be re because there is a DTM that searches through all computations of N on 11 rst of one step then of two steps and so on If 11 E A D will eventually nd an accepting computation If not it will search forever What about an NTMbased de nition of recursive or Turingdecidable sets This is less clear because NTM s don t decide they just have a range of possible actions But one can de ne a function computed by an NTM in a reasonable way and this leads to the same classes of partial recursive functions total recursive functions and recursive sets CMPSCI 601 Unsolvable Problems Lecture 9 We show that a particular language is recursive or re by exhibiting a Turing machine and showing that it decides or accepts the language Note that exhibiting means proving the existence of rather than giving a state ta ble for and we may use highlevel language to prove that existence We want to show that certain languages are not recursive or re which means showing that no possible Turing ma chine can decide or accept them The basic process will be to reduce an already unsolvable problem to the target problem showing the latter unsolv able But clearly we need to start somewhere by showing some problem to be unsolvable in some other way Later in this lecture we ll see the standard example of an unsolvable problem the halting problem of determin ing whether a given TM will halt on a given input But rst since many of you have seen the halting problem before we will show a different related problem to be unsolvable CMPSCI 601 Busy Beaver Function Lecture 9 De nition 93 Suppose we start an nstate TM with tape alphabet 0 1 on a tape with all zeroes We de ne the busy beaver function 001 to be the maximum number of ones left on the tape by any of the nstate TM s that halt in this situation Note that to t our de nitions 0 is now the blank character A Note that C71 is well de ned There are only nitely many nstate TMs with Z 2 0 1 Some nite subset Fm of these eventually halt on input 0 Some element of Fn prints the maximum number of 1 s on the tape and this number is 0n Q1 Q2 Q3 0 qQ1 gt Q30 gt Q31lt 1 h1 qQ1 gt q11lt Q1 Q2 Q3 03 2 6 Q3 Q3 Q1 Q2 Q2 Q2 Q2 Q3 Q3 Q3 Q1 h Imam 1 1 m 11 mm E111 10 11 1 111 1111 1111 m 0 1111m1 o 0 11111 IEEEEEE I III I EEE I lEIa a Hala a Hala I I E I a a II III III IIE EEKa E33 0 I I I I E I I I O E I How quickly does C71 grow as 71 gets large Is C71 E 0012 0073 02quot 001 022 oltexpltngtgt CMPSCI 601 Some Values of 0 Lecture 9 States Max of 1 s Lower Bound for C71 3 03 6 4 04 13 5 05 2 4098 6 06 gt 10835 See the web pages of Penousal Machado eden dei uc pt machado and Heiner Marxen WWW drb insel deNheinerBB for more on this problem and its variants Theorem 94 Let f N gt N be any total recursive function T hen Thatis 2 00n Proof Let you n Hgfm Note h Z 0 quot m 901 We will Show that for all suf ciently large n 071 2 901 First note that since f is total recursive and 9 depends on f in a simple way it is easy to design a TM that computes Let k be the number of states in this TM For any 11 de ne the TM On 2 print n compu te 9 tgl ggy Hog M k 17 0 has log n k 17 states 0 prints gn 1 s Once n is big enough that n 2 log n k 17 can 2 omegni k17gt 2 you CMPSCI 601 A Pairing Function Lecture 9 We have mentioned type casting of the input or output of Turing machines For example we want to think of numbers as strings or strings as numbers so we have 1 1 onto functions to convert one to another Very often we want to think of pairs or sequences of numbers as single numbers So we need a function to convert a pair to a single number and functions to take a number and nd the left or right element of the pair it represents PNXNN onto Thus the input to a Turing machine is a single binary string which may be thought of as a natural number a pair of natural numbers a triple of natural numbers and so forth Later we will worry about the complexity of the pairing and stringconversion functions do you think they are in L Some years ago a CMPSCI 601 student wrote a Java ap plet that calculates these functions You are welcome to play with the applet at immermancs60lchandlerhtml CMPSCI 601 Numbering Turing Machines Lecture 9 Turing machines can be encoded as character strings which can be encoded as binary strings which can be encoded as natural numbers TM 1 2 3 4 O 10 gt 3LJ gt 00 00 1 11 gt 41J gt 01 01 LJ 2LJlt 0LJ 10lt 11lt 1gt 1Igt gt 0Igt 0Igt 01gt ASCII 10 gt11 gt2LJlt 1Igt gt 0Igt 01 21 N 11 There is a simple countable listing of all TM s M0 M1 M2 CMPSCI 601 The Universal Turing Machine Lecture 9 Theorem 95 There is a Universal Turing Machine U such that WWW MW Proof Given mm compute n and m n is a binary string encoding the state table of TM Mn We can simu late Mn on input m by keeping track of its state its tape and looking at its state table 17 at each simulated step Of course we may use multiple tapes to do this A Brookshear s 1979 textbook has a complete diagram for a universal Turing machine on two pages Lewis and Pa padimitriou s 1981 book has a pretty complete descrip tion of one Let s now look at LU the set of numbers Pn m such that the Turing machine Mn eventually halts on input 77 We ll call this language HALT The existence of U proves that HALT is re and now we will prove that it s not recursive HALT 2 Pnm TM eventually halts Theorem 96 Unsolvability of the Halting Problem HALT is 1 16 but not recursive Proof First proof based on busybeaver result HALT 2 w U eventually halts w 1 U w1 U 2 U erase tape print 1 Suppose HALT were recursive Then 0n would be a total recursive function Cycle through all nstate TMs Mi and if Pz39 0 E HALT then count the number of 1 s in Return the maximum of these But 0n isn t total recursive so we have a contradiction A Lecture 9 Listing All re Sets CMPSCI 601 1 can be arranged The set of all re sets W0 W1 W2 in an in nite twodimensional array Wm W0 W1 W2 W3 K F 80110 01 70101000E0 01 6011000l00 10 501010E000 01 401101000 01 3010l00100 10 201l001000 10 n012345678 16 CMPSCI 601 Diagonalization and Halting Lecture 9 K 2 n Mnn21 n1UPnan1 2 n nEWn Theorem 97 F13 7101716 Proof F 2 n n g2 Wm Suppose F were re Then for some 0 F 2 WC 2 nMCn21 CEK lt2 Mcc21 lt2 CEWC lt2 c6 Corollary 98 K E re Recursive Theorem 99 HALT is still not recursive Proof Second proof based on diagonalization If HALT were we recursive we could use a decider for HALT to build a decider for K 2 n n E How But that would make K recursive and thus would make F re contradicting the theorem above So the HALT decider cannot exist A CMPSCI 601 Recall Circuit Complexity Lecture 24 depth parallel time width hardware number of gates computational work sequential time Theorem For alli CRAMlogni ACi AC0 g Thc0 g NC1 g L g NL g sAC1 g AC1 g ThC1 g NC2 g sAC2 g gNCi OACi orhci NC g P NCtn ParallelTimetn on real hardware ACtn CRAMtn ThCtn ParallelTimetn on wetware sAC i ACi but gates bounded AlternationCircuit Theorem Forz 2 l NCi equals ATM s with Olog n space Ologi n time ACi equals ATM s with Olog n space Ologi n al ternations Proof Simulate ATM s by circuits by making a node for each con guration Simulate circuits by ATM s using the Circuit Game Note the AC0 case of the statement of this theorem is false AC0 is not equal to ATM s with Olog n space and 01 alternations that s the logspace hierarchy known by ImmermanSzelepcsenyi to be just NL What AC0 actually equals is the logtime hierarchy ATM s with Olog n time and 01 alternations This is also equal to F0 given the suitable precise de nitions sAC Circuit or and or and Of unbounded 0r s bounded and s Fact 241 sAC1 LOGCFL A 1 ECFL LA g 13 l CMPSCI601 Alternation and CFL S Lecture 24 We ll conclude the discussion of parallel complexity by showing where another one of our existing classes the contextfree languages t into the NC hierarchy Theorem 242 Ruzzo If G is any contextfree grammar G E sACl Proof Using the AltemationCircuit theorem we ll prove this by designing an ATM game for G that has the fol lowing properties White wins the game on input 71 iff w 6 30 0 the game uses Olog n space 0 the number of alternations is Olog n and 0 all Black s alternation phases consist of a single bit move When we covert this game to a circuit the last clause ensures that all the AND gates have fanin two so we are in sACl Though our best upper bound for REACH is also sACl it is believed that REACH is not complete for sAC39lL while there are CFL s that are complete for it 4 Let s assume G is in Chomsky normal form We have an input string 11 and White claims there is a way to derive S gt 11 using the rules of G Black as usual disputes this White advances her claim by naming a node in the middle of the parse tree and saying what it does Speci cally for some 239 j and A she says 539 gt 1111 wiij1 21 and A gt w 21 Black picks one of these two claims to challenge If White is telling the truth about the orginal claim she can get two true claims by telling the truth But if she is lying one of her two subsidiary claims must be a lie We continue the process until we have a claim about a single input letter such as A gt 11 which can be veri ed by looking up the input letter and checking the rules of G This is a valid ATM game that decides whether 11 6 30 but it does not yet meet our speci cation There are two problems 0 The game could last as long as n 1 moves rather than the Olog n we need and 0 The subclaim under dispute might not be speci able in space Olog n as it has the form A gt wil wigBwig 7112407155 We need Olog n bits to record each scar in the string We solve the rst problem by setting a fair time limit on White If she has not reduced the claim to one letter in Olog n moves she loses But why is this fair On her move she is dividing the parse tree of 11 into two pieces by cutting an edge Lemma LiptonTarjan Any binary tree can be cut on some edge into two pieces each at most 23 the original size Proof on HW8 So since White is so smart she can choose her division to leave smaller subtrees and after Olog n moves she can reduce the subtree to one node 6 To solve the second problem we force White to make sure that the current claim is about a tree with at most three scars giving her Olog n more moves to spend on this goal Lemma Let T be any rooted binary tree and let a b and c be any three nodes none of which is an ancestor of another Then there exists a node d that is an ancestor of exactly two of a b and 0 Proof on HW8 Now if White is faced with a tree with scars at a b and c we force her to nd some d and divide the tree there This may not shrink the tree under dispute very much but it makes sure that on the next move the two subclaims have only two scars each White still wins the revised game iff she should and the revised game now ts all the speci cations A CMPSCI601 O1Depth Threshold Circuits Lecture 24 What we call ThCi here is often called TCi elsewhere ThC0 is the set of languages solvable by threshold cirucits of poly size and constant depth We proved ThC0 g NCL by showing how to add n nbit numbers in NCl using ambiguous binary notation base two with digits 0123 This has the effect that there are now many different funny ways to write the same number The idea is that we can add two funny numbers in NC so add n of them in N01 and nally convert the funny result to standard binary in AC0 g NCl 7 I mangled that proof slightly last lecture and will x it now Remember that we want to add two funny num bers and get a funny result without having to propagate carries First in each column 239 we add two numbers from 0 1 2 3 to get a result 7quot in the range from 0 through 6 We will carry a number 03 and keep 7 2c for this columns re sult But we have to choose 03 carefully to avoid carry propagation our goal is that for each 239 the nal result 7quot 20239 ci1 will be in 0 1 2 3 How does column 239 set 03 The principle is that each column will carry as much as it knows that it can safely up to 3 So the column looks at TF1 2 adds it to n and sets 0 to be the minimum of 3 and that sum over 2 Since ci1 will be at least what it expected 03 won t be too large And since ci1 can be only two more than expected 0 won t be too small Some problems in TC 0 Addition of two 72bit numbers is in F0 AC0 the carry lookahead adder Addition of n nbit numbers is in ThC0 AC0 by ambiguous notation 0 Multiplication of two 71bit numbers is in ThCO AC0 0 Sorting of n nbit numbers is in ThCO Compare each of the 722 pairs in parallel then count up the Wins for each item to get its place 0 Division and iterated multiplication of two 71bit num bers to n bits of accuracy is in polynomialtime uni form ThCO BCH86 Reif87 using Chinese re mainder notation 0 Division is in rstorder uniform ThCO Bill HesseOl HAB02 CMPSCI 601 PSPAC E Lecture 24 PSPACE DSPACEn0lt1gt NSPACEn0lt1gt 0 PSPACE consists of what we could compute with a feasible amount of hardware but with no time limit 0 PSPACE is a large and very robust complexity class 0 With polynomially many bits of memory we can search any implicitlyde ned graph of exponential size This leads to complete problems such as reachability on exponentiallylarge graphs 0 We can search the game tree of any board game whose con gurations are describable with polynomiallymany bits This leads to complete problems concerning win ning strategies CMPSCI 601 PSPACEComplete Problems Lecture 24 Recall Lecture 22 PSPACE ATIMEn0lt1gt Recall QSAT the quanti ed satis ability problem Proposition 243 QSAT is PSPACEcomplete Proof QSAT is in ATIMEn Lecture 22 QSAT is hard for ATIME Let M be an arbitrary ATIME machine Let M write down its nk alternating choices 162 an and then deterrninistically evaluate its input using the choice vector 6 Let the corresponding DTIMEW machine be D For all inputs w l 42gt 301V02 ancnkDcw 1 By the proof of Cook s Theorem there is a reduction f from D to SAT Dcw 1 ltgt ow 6 SAT Let the new boolean variables in f c 11 be d1 dtm M accepts w iff 301V02 ancnkXEldl dtnfc w E QSAT Q GEOGRAPHY is a game with players E and A played on a directed graph with start node 3 l E chooses a vertex 111 with an edge from s 2 A chooses v2 having an edge from 111 3 E chooses v3 have an edge from m And so on No vertex may be chosen twice Whoever moves last Wins Texas Selma Africa Transylvania Proposition 244 Figuring out which player has a win ning strategy in a given position of GEOGRAPHY is 14 PSPACEcomplete Proof GEOGRAPHY E PSPACE search the polynomial depth game tree Show QSAT g GEOGRAPHY Given formula 0 build graph G90 st E chooses existen tial variables A chooses universal variables eg p z ElaVbElca v b 13 v c b v 5 avb De nition 245 A succinct representation of a graph is 0010 V E s t where C is a boolean circuit with 272 inputs and V w1w601 E wvw i Cwvw1 SUCCINCT REACH n C st 1 Gm C e REACH Q Proposition 246 SUCCINCT REACH is PSPACEcomplete Proof This is assigned as a problem on Homework 8 A Suitably generalized to n by n versions G0 and Chess are also both PSPACEcomplete In general an n by n game where the playing board can change is going to be PSPACEcomplete because it can simulate alternating polytime A game where 01 pieces move around on a board is going to be Pcomplete because it can simulate alternating log space CMPSCI 601 Barrington s Theorem Lecture 24 A permutation of a nite set S is a onetoone onto func tion from S to itself The composition of two permuta tions is the permutation we get by performing rst one and then the next Composition is not commutative the set of all permutations of ve elements form the non commutative group S5 with composition as the operation The S5 iterated multiplication problem 55MULT is to input n elements of S5 in order and determine their composition Clearly a DFA can do this so 55MULT is a regular language Theorem 247 55MULT is complete for NCl Specif ically if C is an ninput circuit of depth d ana fanin two we can take a string a of length n and construct a sequence of 4d permutations that multiplies to a non ia entitypermutation l Notation A vecycle is abode is the permutation that takes a to b b to c c to d d to e and e to a where abcde 12345 Lemma There exist vecycles a and tau such that 07017 1 is a vecycle This permutation is called the commutator of a and 739 Proof 12345135425432124531 13254 Fact basic group theory If a and are both ve cycles then a 39y 39yl for some permutation 39y Proof of Barrington s Theorem Use induction on the depth d of the circuit For each gate 9 we ll construct a sequence 39 such that 39 evaluates to a vecycle if 9 evaluates to l and 3 9 evaluates to the identity otherwise By the Fact if we can get one vecycle we can get any other with a sequence of the same length Base Case d 0 and the gate is an input Look up the literal and let 39 consist of one permutation 12345 if the literal is true and the identity if it is false NOT Gates If h is the NOT of 9 compose 39 with 54321 This gives the identity if 9 is true and 54321 if 9 is false Using the Fact normalize to give 12345 if h is true and the identity if h is false 20 AND Gates Suppose h is the AND of 91 and 92 and each ofgL and 92 have depth d Using 391 and 392 we construct four sequences of length 4d each 0 a1 yields 12345 if 91 is true and the identity other wise a2 yields 13542 if 92 is true and the identity other wise 1 yields 54321 if 91 is true and the identity other wise and 0 2 yields 24531 if 92 is true and the identity other wise Calculation aaagblbg yields 13254 if 91 and 92 are both true and the identity otherwise Conclusion If C is a depth Olog n circuit we get a sequence of length 40mg which is polynomial We have reduced the circuit evaluation problem to an S5 MULT instance that is only polynomial size A 21 Application to PSPACE Fact PSPACE is characterized by circuits of polyno mial depth Corollary Any PSPACE problem can be reduced to an instance of 55MULT of length 20lt10g n Corollary CaiFurst Any PSPACE problem can be solved by a logspace Turing machine that 0 has access to a readonly clock 0 wipes its memory every polymany steps except for three safe bits 22 CMPSCI 601 Recall From Last Time Lecture 17 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 CMPSCI601 NSPACE VS DSPACE Lecture 17 Proposition 171 NSPACE8n g NTIME20S g DSPACE2Osn We can do much better Theorem 172 REACH e DSPACE1ogn2 Proof G e REACH ltgt G PATHstn PATHcy1 E 2912 Ecy PATHy2d E 32PATHZd PATHZyd Sn d space to check paths of distance d in graphs with n nodes 50171 lognSnn2 010g 2 7mmembemmgmo mammwemmymmhdgmmm for REACH ef cient for deterministic space but lousy nt ne boolean isPath vertex s vertex t int dist if s t return true if dist 1 return edges t else for vertex u O u lt n u if isPath s u dist2 ampamp isPath u t dist dist2 return true return false Thecdlpathstn lreunamtoadq hofahnom log 71 Each recursive call needs Olog 71 bits on the stack mrmmmgumemg masmwas n mm mmam in effect log n nested loops Corollary 173 Savitch s Theorem For 3n 2 log n DSPACEsn g NSPACEsn C DSPACEsn2 Proof Let A E NSPACEsn A N w E A ltigt 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 CMPSCI 601 ImmermanSzelepcs nyi Thm Lecture 17 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 they were not no one looked for a proof that they were 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 re sult might be true Neil reports that he got the basic idea while out walking his dog Theorem 174 REACH E NL Proof Fix graph G Nd H22 1 v reachable from s using 3 d edges Claim The following problems are 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 vertices v y 1 with DISTv d Claim We can compute Nd in NL Proof By induction on d Base case N0 1 Inductive step Suppose we have Nd 1 C 0 2 forv 1t0n d0 3 OR DISTvd1 C 4 VZNDISTZ d Nd 2 3A U IEZ 5 6 7 Nd1 C G e REACH ltgt NDISTtn N 4 Corollary 175 ImmermanSzelepcs nyi Theorem Let 3n 2 log n Then NSPACEsn coNSPACEsn Proof Let A E NSPACEsn A N w E A ltigt C0mpGraphN w E REACH 1w n 1C0mpGraphN 211 20S Testing if C0mpGraphN w E REACH takes space log1C0mpGraphNw1 log208 08n CMPSCI 601 Review Of Reductions Lecture 17 De nition 176 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 A0317 n 1 Claim K S A0317 Proof De ne f as follows erase input if 1 then write 17 M n write n M else 100p n E K ltgt 1 ltgt 17 Q Theorem 177 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 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 Reductions are Useful for Lower Bounds HA is hard and A g B Then B is hard Upper Bounds If B is easy and A g B Then A is easy A Nontrivial Fact About Logspace Reductions Ing Banng amenlg C 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 On HW6 you ll prove that this fact is actually true

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

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

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

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