Class Note for CMPSCI 601 at UMass(51)
Class Note for CMPSCI 601 at UMass(51)
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 14 views.
Reviews for Class Note for CMPSCI 601 at UMass(51)
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 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 I 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 sACi 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 01 and or and or Kn O O O O O O my 7 7 O O O 7 b1 b b b b 2 b n 1 2 n unbounded 0r s bounded and s Fact 241 sAC1 LOGCFL A 1 ECFL LA g 13 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 CMPSCI 601 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 10 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 11 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 12 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 A 13 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 15 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 l6 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 17 CMPSCI601 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 18 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 19 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
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'