Computer Science Theory Final. Spring 2021
You have 180 minutes. The exam is open book but closed to everything else (the Internet in particular). Unless emphasized explicitly, no proof or justification is needed for your answers. Below: DTM means deterministic TM and NTM means nondeterministic TM.
1. [32 points, 4 points per item] Let A and B be two languages. Suppose there is a mapping reduction from A to B. Which of the following can we infer? No justification is needed.
(a) If B is Turing-decidable then A is Turing-decidable. (b) If A is Turing-decidable then B is Turing-decidable.
Copyright By PowCoder代写 加微信 powcoder
(c) IfBisinP,thenAisinP. (d)IfAisinP,thenBisinP.
Suppose there is a polynomial-time reduction from A to B. Which of the following can we infer?
No justification is needed.
(e) If B is Turing-decidable then A is Turing-decidable. (f) If A is Turing-decidable then B is Turing-decidable.
(g) IfBisinP,thenAisinP. (h)IfAisinP,thenBisinP.
2. [20 points, 10 points per item] Let L be the following language:
⟨M,w,q⟩ : M is a DTM, w is a string, q is a state of M,
and q is used at least once during the execution of M on w.
(a) Prove that L is not Turing-decidable. (b) Prove that L is Turing-recognizable.
3. [10 points] We say that a language A has a short-proof polynomial-time verifier V if V is a polynomial-time verifier for A and has the additional property that the length of the proof (or certificate) string c is no longer than O(log n), where n = |w| is as usual the length of the input string w. (Recall in the original definition of polynomial-time verifiers, c is bounded from above by some polynomial of n.) Prove that A ∈ P if A has a short-proof polynomial-time verifier V .
4. [18 points, 8 for NP membership] Let Even-Clique denote the following language:
⟨G, k⟩ : G is an undirected graph, k is a positive integer and G has a clique of size 2k.
Prove that Even-Clique is NP-complete. (Hint: Reduce from Clique.)
5. [20 points, 10 points per item] A polynomial-time three-way NTM M is a polynomial-time NTM with three (instead of two) possible outcomes: accept, reject, and maybe (consider them as three special states qaccept,qreject and qmaybe at which M may halt). We say such a machine decides a language L if the following is true: If x ∈ L, then all branches of M end up with accept or maybe, and at least one with accept; If x ∈/ L, then all branches end up with reject or maybe, and at least one with reject.
(a) Show that if L is decided by a polynomial-time three-way NTM, then L ∈ NP and L ∈ NP. (b) Show that if L ∈ NP and L ∈ NP, then L is decided by a polynomial-time three-way NTM.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com