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!