Name:
Due date: 4:00 P.M., Wednesday, May 6, 1998.
You are permitted to discuss homework with other members of the class, or others outside the class. But the purpose of this discussion should be to enlighten you (or the other person, if a member of the class) about the material, not for one person to simply do another person's homework.
1. Let L_sat be Boolean Satisfiability, and let L_3-sat be the subset of that language consisting of satisfiable formulae of the form C_1 C_2 ... C_n, where each ``clause'' C_i is of the form (a_1+a_2+a_3), where each a_i is the form either x_j or x_j for some j. Prove that L_3-sat is NP-complete.
Hints
2. Let L={1}, the language consisting of just one string, namely 1.
(a) Is L in class NP?
(b) We can reduce L_sat to L as follows. Let M be a machine that decides whether a string w is in L_sat. If it is, M outputs 1, otherwise 0. Is that actually a reduction of L_sat to L?
(c) Given the above answers, we have proved that L is NP-complete. Or have we?
3. There is a Turing Machine emulator on the world-wide web.
(a) Let Sigma={0,1}. Let $f:Sigma*-->Sigma* be the function which squeezes out zeros. That is, if w=0110111100 then f(w) = 111111.
Write the code for a Turing Machine M_f which computes f. Input that code to the emulator on the web, and run it for some examples.
(b)Using the same emulator, write the code for a Turing Machine that accepts the language
{a^n b^n c^n}.