Discrete Math

1. [2 points] Let L = {hMi : M has an even number of states}. Is L decidable? Give a brief explanation
for your answer.
2. [2 points] Let L = {hMi : L(M) has an even number of elements}. Is L decidable? Give a brief
explanation for your answer.
3. [4 points] Consider two languages L1 and L2 such that L1 L2 = !. Show that if L1 and L2
are both recursively enumerable, then there exists a decidable language L such that L1 ✓ L and L2 ✓ L.
4. [3 points] Let 3-SAT-BOUNDED be defined as
3-SAT-BOUNDED = {! : ! is a satisfiable 3-CNF and every variable appears in at most 100 clauses}.
Show that 3-SAT-BOUNDED is NP-complete.
Hint: Consider the CNF ! = (x1 _ x2 _ x3) ^ (x1 _ x2 _ x4). In this 3-CNF, the variable x1 and
x2 appear in two clauses whereas x3 and x4 in one of the clauses. For the version of 3-SAT we showed
to be NP-complete in the class, there might be a variable which can appear in say all the clauses, or
half of the clauses. In order to prove 3-SAT-BOUNDED is NP-complete, show that given any 3-CNF
!, there is an equivalent 3-CNF !0 in which every variable appears in at most 100 clauses and !0 is
satisfiable if and only if ! is satisfiable. Also, the number 100 is irrelevant. If you can do the reduction
with a larger number (say 1000), I will accept that.
5.(a) [2 points] Show that L = {hMi||L(M)| ‘ 2} is recursively enumerable.
5.(b)[2 points] Show that L = {hMi||L(M)| = 2} is not recursively enumerable.
6. [5 points] A function f : {0, 1}⇤ ! {0, 1}⇤ is said to be length-preserving if for all x 2 {0, 1}⇤,
|f(x)| = |x|. In other words, for any n, strings of length n get mapped to strings of length n under the
map f. Further, assume that
• f is one-one.
1
• f is onto.
• f is polynomial time computable.
Note that the first two bullets ensure that f #1 : {0, 1}⇤ ! {0, 1}⇤ is a well-defined function which is

also
one-one, onto and length-preserving. However, it need not be polynomial time computable. Further,
let g : {0, 1}⇤ ! {0, 1} be another polynomial time computable function.
• Prove that L = {y|g(f #1(y)) = 1} is in NP.
• Prove that L = {y|g(f #1(y)) 6= 1} is in NP.
Hint: Please make sure that your “proof” does not somehow require f #1 to be e!ciently computable.
7.(a) [1 point] Suppose you come up with an algorithm running in time 2O(
pn) for 3-SAT (where
the input length is n). Will it necessarily imply that for all L 2 NP, L admits an algorithm of running
time 2O(
pn)
? (where n is the length of the instance in L). Reason briefly.
7. (b) [1 point] Suppose you come up with an algorithm running in time nO(log n) for 3-SAT (where
the input length is n). Will it necessarily imply that for all L 2 NP, L admits an algorithm of running
time nO(log n)
? (where n is the length of the instance in L). Reason briefly.
8. [2 points] Let B = {hM1, M2i|L(M1) = L(M2)}. Show that B is undecidable.
9. [1 point] Let L 2 NP. If P = NP, is L 2 P? If P 6= NP, is L 2 P? (justify briefly).

PLACE THIS ORDER OR A SIMILAR ORDER WITH US TODAY AND GET A GOOD DISCOUNT