15-451 Algorithms 11/18/09 recitation notes * hand back quizzes, hwk5, etc. * number-theory practice * A little more complexity theory [and anything else you want to do] ==================================================================== Go over quiz... More number-theory practice =========================== A *generator* for Z_n^* is a number whose order is phi(n) (the size of the group). It turns out that if n is prime, there is always a generator. Can you find a generator mod 17? 2 doesn't work since its order is 8. (You get 1, 2, 4, 8, 16, 15, 13, 9). How about trying some number not in this list. Write down the whole sequence 1, a, a^2, .... See how it relates to the sequence above. Where is a^{-1} in the list? A little more complexity theory =============================== Turns out there are a number of interesting complexity classes that you can define in terms of a polynomial-time algorithm V that takes in two inputs: an instance I, and an auxiliary string w, where we assume that the length of w is polynomial in the size of the instance. NP: A is in NP if there is a polynomial-time algorithm V(I,w) such that: If "I" is in YES_A, then there exists w such that V(I,w) = YES. If "I" is in NO_A, then for all w, V(I,w) = NO. Co-NP: other way around from NP: If "I" is in YES_A, then for all w, V(I,w) = YES. If "I" is in NO_A, then there exists w such that V(I,w) = NO. RP (randomized polynomial time): A is in RP if exists poly-time V s.t.: If "I" is in YES_A, then for at least half of w, V(I,w) = YES. If "I" is in NO_A, then for all w, V(I,w) = NO. We showed COMPOSITENESS (yes-instances are composites, no-instances are primes) is in RP. Co-RP: the other way around. We showed PRIMALITY (yes-instances are primes, no-instances are composites) is in co-RP. BPP: two-sided error If "I" is in YES_A, then for at least 2/3 of w, V(I,w) = YES. If "I" is in NO_A, then for at least 2/3 of w, V(I,w) = NO. SOME MORE INTERESTING COMPLEXITY CLASSES ======================================== P^{NP} = what you can do in polynomial-time given access to an oracle for solving circuit-SAT. (You just pay 1 unit for each oracle call). P^{#P} = what you can do in polynomial-time given access to an oracle for the problem "Given a circuit C, HOW MANY inputs y have C(y)=1?" PSPACE = what you can do in polynomial work-space (but possibly exponential time). PSPACE contains P^{#P} because we can implement the oracle by just running the circuit on each of the 2^n different inputs one at a time, and incrementing a counter every time we get an output of 1. This takes a long time, but not a lot of work-space. Canonical PSPACE-complete problem: Does the first player have a winning strategy in game X (where X is a sufficiently interesting game, so long as you ensure the length of the game is polynomial). E.g., "generalized geography": Given a directed graph G and a starting node v_0. Players take turns picking edges: each edge must start where the previous edge left off (the first edge must go out from v_0), and no edge can be picked twice. E.g., think of the nodes as letters and an edge from i to j as the name of a country that starts with letter i and ends with letter j. The first player who can't move loses. Why is this even in PSPACE? You want to know "does there exist a move for me such that for all moves for my opponent, there exists a move for me, etc., so that I win. In polynomial space you can do the game-tree search, propagating back the values. In particular, to calculate if state s is a win for me, we just consider each possible move for me, and recursively calculate whether the resulting state is a win or tie for my opponent. If there exists a move for me such that the recursive answer is "no", then s *is* a winning state for me. Amount of space used is just proportional to the *depth* of the recursion (the length of the game) since we just need to remember the path we came from. This is true even if there may be exponentially many game states. It's not even known if P = PSPACE!