Class Note for CMPSCI 601 at UMass(46)
Class Note for CMPSCI 601 at UMass(46)
Popular in Course
Popular in Department
This 19 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 19 views.
Reviews for Class Note for CMPSCI 601 at UMass(46)
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 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 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 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 A and or and or H O O O O O O my 7 7 o O o 7 b1 b b b b 2 b 11 1 2 n unbounded 0r s bounded and s Fact 251 sAC1 LOGCFL A 1 3aCFLBAg B 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 CMPSCI 601 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 10 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 11 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 12 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 13 CMPSCI 601 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 l4 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 15 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 l6 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 17 Here is the graph G90 where p z 3aVb3ca v b 13 v c b v 5 18 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 19
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'