Reference no: EM131215978

Q1. Let L = {(M): M has an even number of states}. Is L decidable? Give a brief explanation for your answer.

Q2. Let L = {(M): L(M) has an even number of elements}. Is L decidable? Give a brief explanation for your answer.

Q3. Consider two languages L₁ and L₂ such that L₁ ∩ L₂ = Φ. Show that if L₁^- and L₂^- are both recursively enumerable, then there exists a decidable language L such that L₁ ⊆ L and L₂ ⊆ L.

Q4. 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 Φ = (x₁ v x₂ v x₃) ∧ (x₁ v x₂ v x₄). In this 3-CNF, the variable x₁ and x₂ appear in two clauses whereas x₃ and x₄ 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 Φ' in which every variable appears in at most 100 clauses and Φ' 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.

Q5.(a) Show that L = {(M)||L(M)| ≥ 2} is recursively enumerable.

(b) Show that L = {(M)||L(M)| =2} is not recursively enumerable.

Q6. A function f : {0, 1}* → {0, 1}* is said to be length-preserving if for all x ∈ {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.
• 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)) =1} is in NP.

Hint: Please make sure that your "proof" does not somehow require f^-1 to be efficiently computable.

Q7.(a) Suppose you come up with an algorithm running in time 2^O(√n) for 3-SAT (where the input length is n). Will it necessarily imply that for all L ∈ NP, L admits an algorithm of running time 2^O(√n)? (where n is the length of the instance in L). Reason briefly.

(b) Suppose you come up with an algorithm running in time n^{O(log n)} for 3-SAT (where the input length is n). Will it necessarily imply that for all L ∈ NP, L admits an algorithm of running time n^{O(log n)}? (where n is the length of the instance in L). Reason briefly.

Q8. Let B = {(M₁, M₂)|L(M₁)= L(M₂)}. Show that B is undecidable.

Q9. Let L ∈ NP. If P = NP, is L^- ∈ P? If P ≠ NP, is L^- ∈ P?(justify briefly).