COMP4141 Theory of Computation FINAL EXAM — Term 1, 2020

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Theory of Computation (COMP4141)

FINAL EXAM — Term 1, 2020

Question 1                   (7 × 2 = 14 marks)

For each of the following statements answer whether they are TRUE, FALSE, or OPEN (answer not currently known). Answers should be justified.

(a) The following language is decidable:

{(M, N) : M is a DFA and N is a PDA and L(M) C L(N)}

(b) There exists a recursively enumerable language whose complement is regular.

(c) Any countable union of recursively enumerable languages is recursively enumer- able.

(d) If P = NP then all languages in P are NP-complete. (e) NL = AP

(f) NP C TIME(2O(n) )

(g) If P = PSPACE then NP = BPP

Question 2                     (3 × 5 = 15 marks)

Are the following languages regular, context-free but not regular, or not context-free? Justify your answer:

(a)  {0n 1m   : n, m > 1 and n = m (mod 3)}

(b)  {0n 1m   : n, m > 1 and n = 3(mod m)}

(c)  {0n 1m   : n, m > 1 and n = m div 3}

Question 3                  (14 marks)

Show that the following language is not in coRE:

Input: A Turing Machine M

Question: Does M halt in the reject state on input e?

Question 4

Show that the following problem is NP-complete:

(15 marks)

Input: A finite collection C of finite sets, and a number k <

ICI.

Question: Does C contain k sets S1, . . . , Sk such that Si U Sj = O whenever i j?

Question 5

(2 × 7 = 14 marks)

Let MIN be the set of formulas φ of propositional logic such that there does not exist a shorter formula φ with φ = φ . (Here φ = φ means that the formulas are logically equivalent, i.e. they take the same truth value for all assignments of truth value to the variables.)

(a) Show that MIN e PSPACE

(b) Explain why the following argument does not show that MIN e coNP:

If φ \e MIN then there exists a shorter equivalent formula φ . A nonde- terministic machine can verify that φ \e MIN by guessing that formula.

Question 6

(2 × 7 = 14 marks)

(a) Show that the complement of an NP-complete language is coNP-complete. (b) Show that for any language A, the complement of a language in NPA is in coNPA .

Question 7                      (2 × 7 = 14 marks)

(a) Show that if L1, L2  e BPP then L1 / L2  e BPP.

(b) Show that if L1, L2  e ZPP then L1 u L2  e ZPP.

2023-04-28