Class Note for CMPSCI 601 at UMass(1)
Class Note for CMPSCI 601 at UMass(1)
Popular in Course
Popular in Department
This 24 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 12 views.
Reviews for Class Note for CMPSCI 601 at UMass(1)
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 25 Theorem All CFL s are in sACl Facts ITADD MULT ITMULT and DIVISION on 71bit integers are all in ThCO Th The following problems are complete for PSPACE NPSPACE ATIMEn0lt1gt QSAT GEOGRAPHY SUCCINCT REACH CMPSCI601 Barrington s Theorem Lecture 25 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 55 with composition as the operation The S5 iterated multiplication problem 55MULT is to input 71 elements of S5 in order and determine their composition Clearly a DFA can do this so 55MULT is a regular language Theorem 251 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 2 1 Notation A vecycle 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 T such that 070 17391 is a vecycle This permutation is called the commutator of a and 739 Proof 12345135425432124531 2 13254 Fact basic group theory If a and are both ve cycles then a 2 y 39y l for some permutation y 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 the vecycle 12345 if 9 evaluates to l and 39 evaluates to the iden tity 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 2 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 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 0 a2 yields 13542 if 92 is true and the identity other wise 0 bl 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 40mgquot which is polynomial We have reduced the circuit evaluation problem to an S5 MULT instance that is only polynomial size A 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 2791 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 CMPSCI 601 Randomization Lecture 25 We see in an algorithms course that it is sometimes to our advantage to use randomness in solving a problem For example Quicksort has good averagecase but bad worstcase behavior Flipping our own coins can with high probability keep us out of the bad cases In a competitive situation we may be worried about our opponent predicting our move Flipping our own coins may make this impossible and guarantee us some mini mum level of expected success Random sampling of a large space may give us a good idea of the results of an impractically large exhaustive search There is a large body of mathematics telling us what inferences we may reliably make from such sam pling Is randomness a powerful tool in general In complex ity theory we attack this question by looking at prob lems where randomization seems practical and compar ing classes of such problems to deterministic and nonde terrninistic classes In a moment we ll look at primality testing which until recently was the most famous example of a problem that could be solved in polynomial time with high probability by a randomized algorithm but which was not known to be in l This example has been taken from us however by Agarwal Saxena and Kayal who last summer gave a deterministic algorithm to test a number for primality in polynomial time P gives two other interesting randomized algorithms 0 Testing whether a matrix of polynomials has determi nant identically zero and 0 Using a random walk through the space of settings to nd a satisfying instance of a 2CNF formula CMPSCI 601 The Primality Problem Lecture 25 PRIME 2 m E N m is prime Proposition 252 PRIME E NP Proof mem ltgt mlt2 3xy1ltacyltm xyzm A Question Is PRIME E NP Fact 253 Fermat s Little Theorem Let p be prime and 0 lt a lt p then cap1 E 1mod p Zquot 2 a 12n 1 GCDan1 n Z is the multiplicative group of integers mod n that are relatively prime to n Euler s Phi 9001 041 0 2 Proposition 254 If n 2 p1 p2 pgk is the prime fac torizaton Ofn then 9001 2 p1 1p2 1 pk 1p1p2 pk Theorem 255 Euler s Theorem For any n and any a 62 Z11 awquot E 1mod n 10 Fact 256 Let p gt 2 be prime Then z is a cyclic group of order p 1 T hat is z 2 aa2a3ap391 m e PRIME 45 3a 6 zgxordm 2 m 1 11 Theorem 257 Pratt PRIME E NP Proof Given m 1Guessa1ltaltm 2 Check am l E 1 mod m by repeated squaring 3 Guess prime factorization m 1 29 m 4 Check forl g 239 g k am39lpi 7 1mod m 5 Recursively check that 191192 pk are prime T01 2 0012 Tn 1 Tn 2 0013 Q Corollary 258 PRIME and Factoring are m NP coNP 12 CS601CM730A More Primality Testing Lecture 25 Leta E Z32 a is a quadratic residue mod m iff 3bb2 E a mod For p prime let a 1 if a is a quadratic residue mod p a 1 otherwise Generalize t0 when m is not prime 7722 21 Z 13 Fact 259 GaussQuadratic Reciprocity For odd a m a l39faE m0d40rm31m0d4 m 03 m0d4andm33m0d4 2 1 ime m0d80rm37m0d8 1 ime m0d80rmE5mod8 14 Thus we can calculate ef ciently g m gr iii 55 1 7ii m 41 1 107 2 351 2 15 2 3 mod 4 107 E 3 mod 8 15 E 7 mod 8 15 Fact 2510 Gauss For p prime a E Z 2 Fact 2511 If m is not prime then a mod p 111 771 1 2 771 1 6 Z 1 2 aTmod lt SolovayStrassen Primality Algorithm 1 Input is odd number m 2 Forz 2 1t0k do 3 choose a lt m at random 4 if GCDa m 1 return n0t prime 5 if 3f amT1mod m return not prime 6 7 return pr0bab1y prime 16 Theorem 2512 0 If m is prime then S0l0vayStrassenm returns probably prime 0 If m is not prime then the probability that Solovay Strassenm returns probably prime is less than 125 Corollary 2513 PRIME E Truly Feasible 17 The new AgarwalSaxenaKayal algorithm is a great the oretical achievement solving an open problem dating back to at least 1970 but is not the best way in practice to test primality SolovayStrassen or the related Miller Rabin algorithm runs faster and gives you numbers that are reasonably certain to be prime If you want a prime of a given size you generate random numbers until you get one that passes the test many times There are enough primes so that you can expect this not to take too long There is a nice FAQ about this new result at cryptocsmcgillca stiglicPRIMESPFAQhtml FACTORING is still believed to be hard for conventional computation But there is a 1994 algorithm due to Shor that solves FACTORING in poly time on a quantum com puter Only very small quantum computers have so far been built but one of them has successfully factored the number 15 18 CS601CM730A Randomized Classes Lecture 25 What does it mean for a problem to be solvable in ran dom polynomial time We can de ne a probabilistic TM easily enough by having an NDTM M ip a coin for each of its classes There are then four different poly time complexity classes de ned in the literature We de ne ProbM as to be the probability that M ac cepts as Remember that A is in NP if there exists M such that ProbM as gt 0 iff a e A The new classes have similar de nitions c A is in RP if there exists M such that ProbM as 2 12 for all a e A and ProbMa 2 0 for all a Q A 0 A is in ZPP ifboth A and A are in RP 0 A is in BPP if there exists M such that ProbM as gt 23 for all a e A and ProbMalt13 for all a Q A 0 A is in PP if there exists M such that ProbM as gt 12 iffa e A 19 CS601CM730A Ampli cation Lecture 25 Which of these classes are practical After all you don t want to put up with a signi cant probability of a wrong answer RP the class generalizing the SolovayStrassen primal ity algorithm is pretty good As we ve seen repeated independent trials can reduce our error probability to ex ponentially small ZPP is even better in one sense because if we try both RP algorithms repeatedly in a constant expected number of trials we will get a guaranteed answer This is his torically called a Las Vegas algorithm provably cor rect probably fast as opposed to an RP or BPP Monte Carlo algorithm probably correct provably fast PP on the other hand is completely useless in practice If the probability of acceptance is very very close to 12 the number of trials needed to make a statistical prediction of whether it is over or under 12 could be exponential 20 But for BPP we are in good shape Proposition 2514 If S E BPP then there is a probabilis tic polynomialtime algorithm A such that for all n and all inputs w of length n 1 if it E S then Pr0bA w 2 l 2 1 7 2n 1 if it a S then Pr0bA w 2 l g 271 Proof Iterate A polynomially many times and answer with the majority The probability the mean is off by g decreases exponentially with n the formal proof uses Chemoff bounds A 21 Is BPP equal to P Probably because pseudorandom number generators are good It s probably possible to build a polytime deterministic generator that gives numbers that are indistinguishable from random to any polytime procedure Such a gener ator would allow us to derandomize BPP It s not hard to show that if a language is in BPP it has nonuniform polysize circuits ie it is in the non uniform class PSIZE This is because if we make the probability small enough that a random string causes the BPP algorithm to be wrong on a given input we can en sure that some string exists that is right on all inputs There exists a circuit that has this string hardwired into it 22 CMPSCI 601 Undirected Reachability Lecture 25 REACH 2 0 undirected sit G Fact 2515 Let be the expected number of steps in a random walk to visit all vertices in connected graph G starting from 239 Then g 2en 1 Corollary 2516 REACH E BPL 23 wwww A look at this directed graph should convince you that a random walk on it is not likely to reach all vertices in polynomial time To get to vertex t from 3 you would have to guess right about 71 times in a row It s very plausible that REACH is in L and one might hope to prove it by derandomizing the random walk There must exist a single sequence of choices of size 0013 that visits every node of any undirected labelled nnode graph But randomization doesn t seem to help much with the general REACH problem 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'