15-451 Algorithms 04/22/09 recitation notes * number-theory practice * NP-completeness reductions contd. ==================================================================== 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? More NP-completeness reductions =============================== Quiz 2 talked about SET-SPLITTING. This turns out to be NP-complete. Let's prove it by reduction from 3-SAT. Given a 3-SAT formula F, create a SET-SPLITTING instance as follows: - one point for each variable x_i and one point for each "not(x_i)". - for each i, make the set {x_i, not(x_i)}. This will force them to be different colors. (One color will represent "true" and the other will represent "false". - one additional point "f" whose color we will interpret as "false". - then, for each clause c in the given 3-SAT formula, we create a set of size 4 containing the literals in c plus the point f. Claim 1: if the 3-SAT formula was satisfiable then the set-splitting instance is solvable too. Proof: use the two colors "true" and "false". Color each literal according to the setting of some satisfying assignment, and color "f" false. Each set has at least one true and at least one false (namely f) so it's a yes-instance too. Claim 2: vice-versa. Just interpret the color of f as false and the other color as true and read off the colors as the assignment. Each clause must have at least one literal set to true, and we never set literals inconsistently because of the sets {x_i, not(x_i)}