15-451 MINI #5: due 11:59pm Thurs November 29, 2007.

1. Number theory practice.

(a) What is 4^{-1} mod 13?  (the multiplicative inverse of 4 in Z_13^*)

(b) Give a number x whose order is 12 over Z_13^*, and write
down the sequence of numbers 1, x, x^2, x^3, ..., x^11 mod 13.  (Such a
number x is called a GENERATOR of Z_13^* since any element in
Z_13^* can be written as a power of x). 

(c) Give a number y whose order is 6 over Z_13^*, and write
down the sequence of numbers 1, y, y^2, y^3, y^4, y^5 mod 13.

2. Strange SAT

(a) Preliminaries [matrix algebra revisited]: Solve the following
set of linear equations over Z_2^* (they're lined up to make the
problem easier to think about): 

       x + y         = 1 (mod 2)
           y + z     = 0 (mod 2)
           y +     w = 1 (mod 2)
       x +     z + w = 0 (mod 2)

 Note that in general, one can solve such systems in polynomial time
 using Gaussian elimination.

(b) We know the problem "Given a CNF formula, does it have a
satisfying assignment?" is NP-complete. In fact, the problem "Given a
CNF formula, does there exist an assignment that satisfies exactly one
literal per clause?" is also NP-complete. However, the problem "Given
a CNF formula, does there exist an assignment that satisfies an odd
number of literals in each clause" *can* be solved in polynomial time.
Why/how?


Comment: By solving 2(b), you've shown the following strange fact.
Say A is the set of CNF formulas that have a satisfying assignment, B
is the set of CNF formulas that have an assignment satisfying an odd
number of literals per clause, and C is the set of CNF formulas that
have an assignment satisfying exactly one literal per clause.  Notice
that C is a subset of B, and B is a subset of A. Your result from 2(b)
implies that even though it is NP-complete to determine whether a
given formula belongs to A, and NP-complete to determine whether a
given formula belongs to C, membership in B can be decided in
polynomial time. This is interesting because given some formula F, if
your algorithm says NO, then we know that it is not in C, and if your
algorithm says YES, then we know that it *is* in A.