Class Note for CMPSCI 601 at UMass(29)
Class Note for CMPSCI 601 at UMass(29)
Popular in Course
Popular in Department
This 22 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 17 views.
Reviews for Class Note for CMPSCI 601 at UMass(29)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CMPSCI 601 Recall From Last Time Lecture 22 De nition Alternating time and space Game Semantics State of machine determines who controls White wants it to accept Black wants it to re ject A w White wins the M game on input 10 Examples 1 MCVP e ASPACElog n 2 QSAT e ATIMEM Theorem For 302 2 log n NSPACEsn g ATIMEsn2 g DSPACEsn2 ASPACEsn DTIME20Squot Corollary ASPACElogn P ATIMEn0lt1gt PSPACE ASPACEn0lt1gt EXPTIME l CMPSCI 601 Parallel Computation Lecture 22 The Turing machine and the abstract RAM are sequential machines in that they perform only one operation at a time Real computers are largely sequential as well but 0 Modern computer networks allow us to apply many processors to the same problem e g SETIhome 0 Modern programming languages allow for parallel eX ecution threads 0 Modern processors are slightly parallel with the ca pacity to do a few things at the same time 0 There have been some experimental massively paral lel computers such as the Connection Machine and 0 The circuit elements inside a given chip operate in parallel Can we solve any problem a million times faster by ap plying a million parallel processors to it Probably not but as with the P vs NP question we don t have any the orems con rming our intuition Parallel complexity theory studies the resources needed to solve problems in parallel To begin such a study we need a formal model of parallel computation analogous to the Turing machine or RAM As it turns out just as the TM and RAM have similar behavior with respect to time and space various differ ent parallel models have similar behavior with respect to parallel time and amount of hardware Parallel Random Access Machines CRAMtn CRcwPRAMTIMEtnHARDn0lt1gt synchronous concurrent read and write uniform 7101 processors and memory priority write lowest number processor wins con ict common write no con icts allowed The alternating Turing machine is another parallel model of sorts since the acceptance behavior depends on the entire set of con gurations The parallel time measure turns out to be the number of alternations between existential and universal states Theorem 221 For logn g tn 3 7101 CRAMtn is equal to the class of languages of ATM s with space Olog n and Otn alternations We won t prove this here I might put it on HW8 but we ll show that ATM s are closely related to another par allel computing model that of boolean circuits CS601CM730A LH and PH Lecture 22 An important special case of ATM computation is when the number of alternations is bound by a constant We use the same names for constantaltemation classes that we de ned for the Arithmetic Hierarchy in HW5 For example ElP consists of the languages of polytime ATM s that always stay in existential states that is NP MP is the same for only universal states that is coNP EgP consists of the languages of polytime ATM s that have a phase of existential con gurations followed by a phase of universals HQP is the complement of 221 and so on PH is de ned to be the union of EZP and HiP for all con stant 239 or languages of polytime ATM s with 01 alter nations Theorem 222 PH 2 SO The proof is a simple generalization of Fagin s Theorem NP 03 The Logtime Hierarchy On HW 7 we re looking at ATM s that operate in Olog n time making key use of their randomaccess input tape You re asked to prove that such an ATM can decide 0 any language in F0 and also 0 the PARITY language of strings with an odd number of 1 s PARITY is not in F0 though we won t be able to prove such a lower bound in this course The complexity class LH the logtime hierarchy is the set of languages decidable in ATIMElog n with 01 alternations Your HW solution will most likely show that FO g LH It turns out that with the right de nition of F0 F0 LH CMPSCI 601 Circuit Complexity Lecture 22 Real computers are built from many copies of small and simple components Circuit complexity uses circuits of boolean logic gates as its model of computation Circuits are directed acyclic graphs Inputs are placed at the leaves Signals proceed up toward the root 7 Straightline code gates are not reused Let S g 0 1 be a decision problem Let 0102022 be a circuit family On has n input bits and one output bit 7 Def EN computes 539 iff for all n and for all to E 07 1quot 7065 4 9 C1w1w1 or and or and or S 3 ton O O my 7 7 O O O 7 b1 b b b b 2 b n l 2 n not gates are pushed down to bottom Depth parallel time Number of gates computational work sequential time CMPSCI 601 Circuit Uniformity Lecture 22 Consider the class PSIZE of languages A that are com puted by a family of polysize circuits That is for each 72 there is a circuit On that accepts an input string to iff w E A It is easy to see from our construction for Fagin s Theo rem that P g PSIZE Also since CVP is in P it seems that PSIZE should be no more powerful than P But as we ve de ned PSIZE it contains undecidable lan guages Look at UK w 1w 6 K for example For any input length 72 there is a one gate circuit that decides Whether the input is in UK it either says yes or says no Without looking at the input at all So UK is in PSIZE but it s clearly recomplete as it s just a recoding of K 10 But this circuit is nonuniform Given a number n it is impossible for any Turing machine much less a poly time TM to determine what On is Let s de ne Pum form PSIZE to be those languages de cided by polytime circuit families where we can com pute On from the string 1quot in 7101 time Now it s easy to see that Puniform PSIZE is contained in P because our machine on input 10 can rst build the circuit CM and then solve the CVP problem that tells what 01w does on input 10 And in fact the tableau construction tells us that P is con tained in Puniform PSIZE because the circuit from the tableau is easy to construct In fact it s very easy to con struct we could do it in FL or even in Thus we have Theorem P Puniform PSIZE Luniform PSIZE FOuniform PSIZE ll De nition 223 The NC Hierarchy Let tn be a poly nomially bounded function and let S Q 0 l Then S is in the circuit complexity class NCtn ACtn 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 49 Clwl w 1 2 The depth of 6 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 12 NCi NClogni AC2 AClogni ThCl ThClognz NC OGNCl OGACZ39 nd 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 s Q s OGACZ39 06 ThCl OGNCl NC 23921 i1 i1 l3 The word uniform above means that the map f lquot r gt 0 is very easy to compute for example f E FL or f E F Though these uniformity conditions are a subj ect dear to my heart we won t worry too much about the details of them in this course Overall NC consists of those problems that can be solved in polylog parallel time on a parallel computer with poly nomially much hardware The question of whether P NC is the second most important open question in com plexity theory after the P 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 NC Theorem CVP MCVP and HORNSAT are all P complete 14 Proposition 224 Every regular language is in NC 1 Proof Given DFA D E Q 6 s Construct circuits 0102 for all 10 E 2 w E D 4 Clw1w1 15 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 16 Theorem 225 BarringtonImmermanStraubing FO AC0 ProofSketch of one direction with some uniformity de tails skipped 99 350Vy3zMayaz 17 Proposition 226 F0ri01 NCZ39 g AC2 g ThCi g NCZ391 Proof All inclusions but ThCi g NCH1 are clear MAJ w 6 01 1 10 has more than 11012 1 s E ThC0 Lemma 227 MAJ 6 NC1 and the same for any other threshold gate 18 The obvious way to try to build an NC1 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 X1 X2 X3 X4 X5 X6 X7 X8 12 l9 A solution to this problem is Via ambiguous arithmetic notation Consider a representation of natural numbers in binan exceptthatc g s 01231nay be used For example 3213 and 3221 are different representations of thmmmnmm 3 nmmmmgmmnmmmu 3213 3221 323222121320 323222221120 20 37 37 Lemma 228 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 21 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 22
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'