Class Note for CMPSCI 601 at UMass(10)
Class Note for CMPSCI 601 at UMass(10)
Popular in Course
Popular in Department
This 23 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 14 views.
Reviews for Class Note for CMPSCI 601 at UMass(10)
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 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 231 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 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 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 2 NClogni ACquot 2 AClogni ThCl ThClogn 6 NC ONCl OACl find 239 i0 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 Q s 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 559539 9 Q 6 gt gb i XXXXXXXX gl 2 12345678 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 10 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 ll CMPSCI 601 Fitting in L and NL Lecture 24 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 we use Olog n space A 12 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 l3 CMPSCI601 The AlternationCircuit Theorem Lecture 24 We know that ASPACElog n 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 14 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 15 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 l6 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 17 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 18 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 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 24
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'