(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) ⊆ 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 ⊆ TIME(2O(n))
(g) IfP=PSPACEthenNP=BPP
(a) FALSE: Taking M to be a DFA that accepts Σ∗ gives a reduction from the universality of CFLs.
(b) TRUE: Any regular language is recursively-enumerable and its complement is regular.
(c) FALSE: All languages are countable
(d) FALSE: ∅ is not NP-complete
(e) FALSE: Space-hierarchy theorem
(f) OPEN: If P = NP then it would be true. If NP = EXPTIME then it would be false as then TIME(2O(n)) ⊆ NP, but TIME(2O(n)) is not closed under polynomial-time many-one reductions so they cannot be equal.
(g) TRUE: If P = PSPACE then the polynomial-time hierarchy collapses and P = NP = BPP = PSPACE.
Question 1
Question 2
(3 × 5 = 15 marks)
Are the following languages regular, context-free but not regular, or not context-free? Justify your answer:
(a) {0n1m : n,m≥1andn≡m(mod3)} (b) {0n1m : n,m≥1andn≡3(modm)}
(c) {0n1m : n,m≥1andn=mdiv3} Solution
(a) The language is regular. Here is an NFA that accepts the language:
Intuitively, the automaton “remembers” n (mod 3) and then checks to make sure m(mod 3) is equal to n(mod 3)
Alternative proof
The language can be written as the union L1 ∪ L2 ∪ L3 where:
L1 = {03k+113j+1 : k, j ∈ N} = L 0(000)∗1(111)∗
L2 = {03k+213j+2 : k, j ∈ N} = L 00(000)∗11(111)∗ L3 = {03k+313j+3 : k, j ∈ N} = L 000(000)∗111(111)∗
From this we can see that the language is matched by the regular expression:
0(000)∗1(111)∗ ∪ 00(000)∗11(111)∗ ∪ 000(000)∗111(111)∗
(b) This language is not context-free. We show this with the pumping lemma
Assume L = {0n1m : n,m ≥ 1 and n ≡ 3(mod m)} is context-free, and sat- isfies the pumping lemma for context-free languages with pumping length p.
We will make use of the following result:
Letp∈Nwithp≥1,andletk=2p+1. Thenforalla,bwith 1 ≤ a ≤ p and 0 ≤ b ≤ p, we have
(k − b) – (k! − a)
Proof of lemma
Assume (k − b)|(k! − a). As (k − b)|k!, this statement is equivalent to saying(k−b)|a. Asa≤pandb≤p,wehave0
3. uvixyiz∈Lforalli∈N.
Suppose u, v, x, y, z satisfy conditions 0, 1 and 2 of the Pumping Lemma. We consider 3 cases:
Case1:voryoftheform0a1b wherea,b>0.
In this case uv2xy2z will not be of the form 0n1m and therefore not in L.
Case 2: uxy is of the form 0k!+31m where m < k Inthiscase,vandyareoftheformv=1a andy=1b whereatleastoneof a,bisgreaterthan0.Now,fori=k!+3,wehaveuvixyiz=0n1m where
• n=k!+3,and • m>k!+3
But then n ≡ k!+3 ̸≡ 3(mod m), so uvixyiz ∈/ L.
Case3: uxyisoftheform0n1m wheren
In all cases, we see that it is not possible to break w into uvxyz such that the conditions of the Pumping Lemma are satisfied. Therefore L is not context-free.
(c) This language is context-free, but not regular. To see that it is context-free, we observe that it can be written as
{0n1m : m=3n+xwherex∈{0,1,2}}.
It follows that the language is generated by the grammar
({S, T}, {0, 1}, R, S) where R is the set of rules: S → 0S111 | 0T111
T → ε|0|00
To show the language is not regular, we will use the Myhill-Nerode theo-
rem. For each i, j ∈ N let: • ui = 0i
• wij = 13i
We see that if i ̸= j then uiwij = 0i13i is in the language, but ujwij = 0j13i is not in the language (as 3i div 3 = i ̸= j). Thus the syntactic equiva- lence relation of the language has infinite index, and by the Myhill-Nerode theorem, the language is not regular.
Question 3
Show that the following language is not in coRE:
Input: A Turing Machine M
Question: Does M halt in the reject state on input ε?
(14 marks)
The language is accepted by the following Turing Machine. On input ⟨M⟩:
1. Simulate M on input ε.
2. If M rejects then accept. If M accepts then reject.
Hence the language is recursively enumerable.
To show that it is undecidable, we show a reduction from the acceptance prob- lem for Turing Machines:
{⟨M, x⟩ : M accepts x}.
Given a pair ⟨M, x⟩ we construct a Turing Machine Mx as follows:
1. On any input y, simulate M with input x.
2. If M accepts x then reject. If M rejects x then accept.
Clearly Mx rejects ε if, and only if, M accepts x. Thus this is a reduction from the acceptance problem to our problem. As we know the acceptance problem for Turing Machines is undecidable, it therefore follows that the our language is also undecidable. Hence it is not decidable.
Question 4 (15 marks) Show that the following problem is NP-complete:
Input: A finite collection C of finite sets, and a number k ≤ |C|. Question:DoesCcontainksetsS1,…,Sk suchthatSi∩Sj =∅wheneveri̸=j?
To show the problem is NP-complete, we must show that it is in NP, and that it is NP-hard.
To show the problem is in NP, consider the following algorithm:
On input C = {T1,T2,…,Tn} and k ≤ n:
• Non-deterministically guess C′ ⊆ C
• Check if |C′| = k. If not then reject.
• CheckifS∩T=∅forallS,T∈C′.Ifnot,thenreject • Accept
This algorithm clearly decides the decision problem with a non-determinstic TM. It remains to show that it runs in polynomial time. If m = max|Ti| and n = |C| then the running time for each of these steps is at most O(n) + O(n) + O(n2m) = O(n2m). As the input has size at least Ω(m + n), the running time of the algorithm is polynomial in the size of the input. Therefore, the problem is in NP.
To show the problem is NP-hard, we give a reduction from Independent Set:
Independent Set
Input: A graph G = (V, E) and an integer k
Question: Does G have a set of vertices V′ ⊆ V such that |V′| ≥ k and for all u,v ∈ V′, {u,v} ∈/ E?
This was shown to be NP-hard in tutorials.
Given an instance ((V, E), k) of Independent set, define the following instance
(C, k′) of our decision problem:
• C={Sv : v∈V}whereSv ={e∈E : v∈e}∪{v}
We can construct (C, k′) from ((V, E), k) in time O(|V||E|), so this is a polynomial-time mapping. Note that if v ̸= w then Sv ̸= Sw. Also, note that Sv∩Sw =∅ifandonlyifvandwdonothaveanedgeincommon–i.e.ifand only if {v, w} ∈/ E.
Suppose ((V, E), k) is a yes-instance which maps to (C, k′). Then there exists an independent set V′ ⊆ V of size at least k in (V,E). As a subset of an independent set is also an independent set, we can assume that V′ is of size exactlyk.ConsiderC′ ={Sv : v∈V′}⊆C.As|V′|=k,wehave|C′|=k=k′. AsV′ isanindpendentset,{v,w}∈/Eforallv,w∈V′,soSv∩Sw =∅forall Sv, Sw ∈ C′. Therefore (C, k′) is a yes-instance of our problem.
Conversely, suppose ((V, E), k) maps to (C, k′) and (C, k′) is a yes-instance. Let C′ ⊆ C be the collection of k′ sets such that Sv ∩Sw = ∅ whenever v ̸= w. Let V′ ⊆Vbethesetofk′ =kverticessuchthatC′ ={Sv : v∈V′}. Then,from the definition of the Sv, it follows that {v, w} ∈/ E for all v, w ∈ V′. Therefore V′ is an independent set of size k. So ((V, E), k) is a yes-instance.
Therefore the mapping is a polynomial-time many-one reduction from Inde- pendent set to our problem; and so the problem is NP-hard.
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 ∈ PSPACE
Code Help
(b) Explain why the following argument does not show that Min ∈ coNP:
If φ ̸∈ Min then there exists a shorter equivalent formula ψ. A nonde-
terministic machine can verify that φ ̸∈ Min by guessing that formula. Solution
(a) In lectures it was shown that Min ∈ Π2P and Π2P ⊆ PSPACE. Therefore Min ∈ PSPACE.
(b) The issue is that the “guessed” formula ψ still needs to be shown to be equivalent to φ (the existence of a shorter formula does not establish that φ ∈/ Min). In order to show the two formulas are equivalent, we must check if they agree on all truth assignments. This can be done non- deterministically – but with a universal non-deterministic step. Whether it is possible to do so with existential non-determinism is, of course, an open problem.
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.
(a) Let L be an NP-complete language, and let L′ denote its complement. Since L∈NP,wehavethatL′ ∈coNP.
To show that L′ is coNP-hard. consider any language K ∈ coNP. Because K ∈ coNP, its complement, K′ is in NP. Because L is NP-hard, there exists a polynomial-time many-one reduction, f, from K′ to L. From the defini- tion of a reduction, we observe that f is also a polynomial-time many-one reduction from K to L′. Therefore, K ≤P L′ and so L′ is coNP-hard.
(b) Let L ∈ NPA. Then there is a non-deterministic, oracle-for-A Turing Ma- chine M that accepts L in polynomial time. Consider the following co-non- deterministic, oracle-for A Turing Machine M′:
• M′ has the same states as M except the accept and reject states are swapped.
• M′ has the same transitions as M but non-determinism is resolved universally rather than existentially (note: this only affects acceptance).
程序代写 CS代考 加微信: cstutorcs
Oracle queries are handled identically. We observe the following:
w ∈ L(M′) iff
iff all runs of w in M end in M’s reject state
all runs of w in M′ end in M′’s accept state iff no run of w in M ends in M’s accept state
iff w∈/L(M)
Therefore L(M′) = L, and M′ accepts L in polynomial time. Therefore M′ is
a polynomial-time, co-non-determinstic TM that accepts L. So L ∈ coNPA.
Question 7 (2 × 7 = 14 marks)
(a) ShowthatifL1,L2 ∈BPPthenL1\L2 ∈BPP. (b) ShowthatifL1,L2 ∈ZPPthenL1∪L2 ∈ZPP.
(a) If L1, L2 ∈ BPP, let M1 and M2 be bounded-error, polynomial-time, prob- abilistic TMs that probabilistically accept L1 and L2 (respectively). By the Amplification Lemma, we can assume that M1 and M2 have bounded error
16. That is,
• If w ∈ L1 then P(M1 accepts w) ≥ 65, and
• If w ∈/ L1 then P(M1 accepts w) < 16, and similarly for M2.
Consider the following probabilistic Turing Machine M:
On input w:
• Run M1 on w
– If M1 rejects then REJECT • Run M2 on w
– If M2 accepts then REJECT – Else ACCEPT
As M1 and M2 run in polynomial time, M also runs in polynomial time. Also:
• If w ∈ L1 \ L2 then
P(M accepts w) = P(M1 accepts w and M2 rejects w) ≥ 56 · 65 > 23.
• Ifw∈/L1\L2 theneither: – w ∈/ L1, in which case:
P(M rejects w) ≥ P(M1 rejects w) ≥ 56 > 32 – w∈L1∩L2,inwhichcase:
P(M rejects w) ≥ P(M1 accepts w and M2 accepts w) ≥ 56 · 56 > 32 In either case P(M accepts w) = 1 − P(M rejects w) < 13 .
So M probabilistically accepts L1 \ L2 with bounded error. Hence L1 \ L2 ∈ BPP.
(b) If L1,L2 ∈ ZPP then L1,L2 ∈ RP and L1,L2 ∈ coRP. For i = 1,2, let Mi, Ni be the probabilistic polynomial time TMs where:
• Ifw∈Li thenP(Mi acceptsw)>12 andP(Ni acceptsw)=1,and • Ifw∈/Li thenP(Mi acceptsw)=0andP(Ni acceptsw)<21.
That is, Mi shows Li ∈ RP and Ni shows that Li ∈ coRP. Consider the following probabilistic TMs:
On input w:
• RunM1 onw
• RunM2 onw
• If either M1 or M2 accepts then ACCEPT
• Else REJECT
On input w:
• RunN1 onw
• RunN2 onw
• If either N1 or N2 accepts then ACCEPT
• Else REJECT
As Mi and Ni run in polynomial time, it follows that M and N also do. Furthermore:
Programming Help, Add QQ: 749389476
• Ifw∈Li then
– P(M accepts w) ≥ P(Mi accepts w) ≥ 12
– P(N accepts w) ≥ P(Ni accepts w) = 1 • Thereforeifw∈L1∪L2 then
– P(M accepts w) ≥ 21 – P(N accepts w) = 1
• Ontheotherhand,ifw∈/L1∪L2 then
– P(M accepts w) = 0 as neither M1 nor M2 will accept w
– P(N accepts w) ≤ P(N1 accepts w)·P(N2 accepts w) ≤ 21 · 12 < 21
ThusMshowsthatL1∪L2 ∈RPandNshowsthatL1∪L2 ∈coRP.There- fore L1 ∪ L2 ∈ ZPP.
— END OF EXAMINATION — 10