Class Note for CMPSCI 601 at UMass(3)
Class Note for CMPSCI 601 at UMass(3)
Popular in Course
Popular in Department
This 31 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 15 views.
Reviews for Class Note for CMPSCI 601 at UMass(3)
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 26 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 26 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 As a language it is the set of pairs at t such that w E 5 t 6 S5 and w multiplies to t Clearly a DFA can carry out the sequence of multiplications so 55MULT is a regular language Theorem 261 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 alagblbg 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 An 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 entire working memory every polymany steps except for three safe bits CMPSCI 601 Randomization Lecture 26 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 probabil ity by a randomized algorithm but which was not known to be in l This example has been taken from us how ever by Agarwal Saxena and Kayal who in 2002 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 26 PRIME 2 m E N m is prime Proposition 262 PRIME E NP Proof m m ltgt mlt2 3xy1ltacyltm xyzm A Question Is PRIME E NP Fact 263 Fermat s Little Theorem Let p be prime and 0 lt a lt p then cap1 E 1mod p Zquot 2 aE12n 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 264 If n 2 p1 p2 pgk is the prime fac torizaton Ofn then 9001 2 p1 1p2 1 pk 1p1p2 pk Theorem 265 Euler s Theorem For any n and any a E Z11 awquot E 1mod n 10 Fact 266 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 267 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 268 PRIME and Factoring are m NP coNP 12 CS601CM730A More Primality Testing Lecture 26 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 269 GaussQuadratic Reciprocity For odd a m a l39delm0d40rmElmod4 m l39faE3mod4andm33m0d4 a 2 1 l melm0d80rmE7mod8 1 z39meBm0d80rmE5mod8 14 This ZOOyearold result gives us an ef cient way to cal culate a that uses time polynomial in the length of m 7 Fact 2610 Gauss For p prime a E Z a E a mod p p Fact 2611 If m is not prime then a L4 m 1 a E Zm a 2 mod lt 2 SolovayStrassen Primality Algorithm 1 Input is odd number m 2 Forz 2 1tok do 3 choose a lt m at random 4 if GCDa m 1 return not prime 5 if 3f amT1mod m return not prime 6 7 return probab1y prime 15 Theorem 2612 Suppose we run SolovayStrassen on a number m T hen a If m is prime then the answer is always probably prime 1 If m is not prime then the probability of probably prime is less than 12 Corollary 2613 PRIME E Truly Feasible 16 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 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 using something like Shor s method 17 CS601CM730A Randomized Classes Lecture 26 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 e 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 18 CS601CM730A Ampli cation Lecture 26 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 l9 But for BPP we are in good shape Proposition 2614 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 e 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 20 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 21 CMPSCI 601 Undirected Reachability Lecture 26 REACH 2 0 undirected sit G Fact 2615 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 2616 REACH E BPL 22 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 23 CMPSCI 601 Interactive Proofs Lecture 26 Goldwasser Micali Rackoff Babai Decision problem D input string a Two players Prover Merlin is computationally allpowerful Wants to convince Veri er that a E D Veri er Arthur probabilistic polynomialtime TM Wants to know the truth about whether a E D 24 Inputaz n tzn O A has a M has a 1 ip 01 compute m1 gt 2 lt m2 3 ip 03 compute 1713 gt 4 lt 7714 2t lt m2t 2t 1 ip 02t1 acceptor reject 25 De nition 2617 D 6 IP iff there is such a polynomial time interactive protocol 1 If a E D then there exists a strategy for M 2 ProbA accepts gt g 2 If a g D then for all strategies for M 1 ProbA accepts lt g A Observation 2618 Iieraiing makes probabilities of er ror exponentially small Special Cases of IP 0 Deterministic Arthur NP 0 N0 Merlin BPP 26 Graph NonIsomorphism 6 AM Input 00019 n 1100 211011 O A has 0001 M has 0001 1 ipn17 gt 01 lp7l 17l39r 6 8n 71 1C772 1739 39 39 WTGI T gt 2 lt m E 071r 3 accept iff R 2 m2 Proposition 2619 Graph NonIsomorphl39sm 6 AM Proof If GO G 1 then A will accept with probability 1 If GO g G 1 then A will accept with probability 3 2quot A Corollary 2620 If Graph Isomorphism is NPcomplete then PH collapses to 2 2 27 Fact 2621 Shamir s Theorem IP 2 PSPACE proof that IP g PSPACE Evaluate the game tree For M s moves choose the maximum value For A s moves choose the average value 9 m m gg k Hard Direction Construct an interactive proof that a string is in QSAT There are proofs in P and in Sipser 28 CMPSCI 601 Checkable Proofs Lecture 26 Any decision problem D E NP has a deterministic polynomial time veri er By adding randomness to the veri er we can greatly re strict its computational power and the number of bits of H that it needs to look at while still enabling it to accept all of NP We say that a veri er A is Mn qnrestricted iff for all inputs of size n and all proofs H A uses at most Orn random bits and examines at most Oqn bits of its proof H Let PCPrn be the set of boolean queries that are accepted by Mn qnrestricted veri ers Fact 2622 PCP Theorem NP 2 PCPlogn 1 The proof of this theorem is pretty messy certainly more than we can deal with here But we can look at the appli cations of the PCP Theorem to approximation problems 29 MAXBSAT Given a 3CNF formula nd a truth as signment that maximizes the number of true clauses 91 VQZQVQTg 91 V924V3T5 12j xgvmvm T2VaZ3VaZ5T3V9T4VQT5 VTgVacgT2VT4V5 Proposition 2623 MAXBSAT has a polynomialtime 6 2 approximation algorithm Proof Be greedy set each variable in turn to the better value A You can do better a random assignment gets 78 of the clauses Open for Years Assuming NP P is there some 6 0 lt e lt 1 st MAXBSAT has no PTIME eapproximation algorithm 30 Theorem 2624 The PCP theorem NP 2 PCPlog n 1 is equivalent to the fact that If P 2 NP then Forsome 6 1gt 6 gt 0 MAXBSAT has no polynomialtime eapproximation algorithm Fact 2625 MAXBSAT has a PTIME approximation algorithm with e 2 i and no better ratio can be achieved unless P 2 NP References 0 Approximation Algorithms for NP Hara Problems Dorit Hochbaum 6d PWS 1997 0 Juraj Hromkovic Algorithmics for Hard Problems Springer 2001 0 Sanjeev Arora The Approximability ofNPhard Prob lems STOC 98 wwwcsprincetoneduNarora 31
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'