Class Note for CMPSCI 601 at UMass(53)
Class Note for CMPSCI 601 at UMass(53)
Popular in Course
Popular in Department
This 18 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(53)
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 23 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 23 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 eg 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 write con ict crashes machine 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 231 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 a piece of the proof on HW8 but we ll show that ATM s are closely related to another parallel computing model that of boolean cir cuits First however a digression CS601CM730A LH and PH Lecture 23 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 232 PH 2 SO The proof is a simple generalization of Fagin s Theorem NP 03 The Logtime Hierarchy On Spring 2003 s HW 7 we looked at ATM s that op erate in Olog n time making key use of their random access input tape We proved then 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 A careful solution shows that FO g LH It turns out that with the right de nition of F0 F0 LH On this term s HW7 we look at the similar logspace hi erarchy LSH which you ll prove collapses to is equal to NL CMPSCI 601 Circuit Complexity Lecture 23 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 The code is straightme in that gates are not reused be cause the graph is acyclic In fact the boolean straight line programs of Lecture 1 and HWl were simply a re formulation of boolean circuits Circuit Families and Languages Let S g 0 1 be a language or decision problem Let 0102022 be a circuit family Each circuit On has n input bits and one output bit 7 De nition ZEN computes 539 iff for all n and for all to 6 01quot to E S 49 Clw1w1 or and or and or 3 3 tn O O nV 7 7 O O O 7 b1 b b b b 2 b n 1 2 n It turns out that NOT gates in the middle of the circuit can be pushed down to the bottom and eliminated Without changing the parameters of the circuit so we will keep circuits in this form Size and Depth The depth of the circuit is the length of the longest path from an input to an output Compare the depth of an SLP in HWl The depth measures the parallel time the total delay for the circuit to compute its value in terms of the individual gate delays The size of the circuit is the number of gates counting the input gates and their negations This is the length of the corresponding SLP It represents the computational work used to solve the problem and corresponds roughly to the sequential time needed to evaluate the circuit These size and depth parameters become functions of the input size n once we consider a circuit family instead of a single circuit These become our cost measures and we use them to de ne complexity classes 10 CMPSCI 601 Circuit Uniformity Lecture 23 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 11 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 12 De nition 233 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 all 10 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 l3 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 14 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 subject 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 15 Theorem 234 C VP MC VP monotone C VP and HORN SAT are all Pcomplete Proof CVP is the set of pairs 0 3 such that circuit C accepts input string a which must thus be of the right length This is pretty clearly in P because we can evalu ate C gate by gate To reduce an arbitrary P language to CVP we use the tableau construction from the Fagin or CookLevin proofs or from the proof that P is contained in alternating logspace Since each cell of the tableau depends on those just below it and any function of 01 boolean inputs has circuits of 01 size and depth HWl we can build a circuit that computes each cell value The output gate of this circuit tells us whether the machine accepts the input by looking at the rst cell of the tape at the last time step The monotone problem MCVP is clearly still in P To reduce CVP to MCVP we can use doublerail logic For each gate 9 of the orginal circuit C we make two gates one to compute g and the other to compute g If we have done this inductively for g s children it s easy to do it for g with AND and OR gates there are four cases 16 HORNSAT is the language of satis able boolean formu las in HORNCNF AND s of clauses each of which is ofthe forrn 211 3 gt y where the mi s and y are variables not negated We solve it in P with a greedy al gorithm starting with all variables false and setting true only those required by the clauses in successive passes To reduce MCVP to HORNSAT we make a variable for each gate and one or two clauses for the effect of each gate If g is an AND gate with children h and hg we add the Horn clause hl hg gt g Ifg is the OR of h and hg we add h gt g and hg gt 9 We then force the inputs to the correct values and force the output gate s variable to l and we are satis able iff the circuit actually computes 1 Q 17 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 18
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'