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)}