15-451 MINI #5: due 11:59pm Tues 11/24/09 1. Number theory practice. (a) What is 5^{-1} mod 13? (the multiplicative inverse of 5 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 different number y that also has order 12 over Z_13^*, and write down the sequence of numbers 1, y, y^2, y^3, ..., y^11 mod 13. (d) Give a number z whose order is 6 over Z_13^*, and write down the sequence of numbers 1, z, z^2, z^3, z^4, z^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.