Computational Complexity and Computability
Lecture 7 – Closure Properties & Reducibility
Koushik Pal
University of Toronto
February 1, 2021
Closure Properties
Theorem
The class D is closed under union, intersection, concatenation, complementation and Kleene star.
Proof.
Let A, B ∈ D. By definition, there are deciders MA and MB that recognize A and B, respectively.
Define a TM M as follows: On input w:
Run MA on w; if MA rejects, reject. Run MB on w; if MB rejects, reject. Otherwise accept.
Clearly,M isadeciderandL(M)=A∩B. Hence,A∩B∈D. Exercise: Prove the rest.
Closure Properties
Theorem
The class SD is closed under union, intersection, concatenation and Kleene star, but not under complementation.
Proof.
Let A, B ∈ SD. By definition, there are TMs MA and MB that recognize A and B, respectively.
Define a TM M as follows: On input w:
Run MA and MB alternately on w step by step; if either MA or MB accepts, accept.
Clearly,L(M)=A∪B. Hence,A∪B∈SD. Exercise: Prove the rest.
Closure Properties Definition
coSD:={A|Ac ∈SD}. Theorem
D = SD ∩ coSD.
Proof.
(−→)
If A ∈ D, then A = L(M) for some decider M. Naturally, A ∈ SD. Define a TM M′ as follows:
On input w:
Run M on w.
If M accepts, reject; if M rejects, accept.
Clearly, L(M′) = Ac, which implies A ∈ coSD.
Closure Properties
(←−)
Suppose A ∈ SD ∩ coSD. Let E and E′ be enumerators for A and Ac, respectively. Then A is decided by a TM which, on input w, runs E and E′ in parallel and accepts or rejects based on which enumerator outputs w.
DIAG and ATM
Definition
DIAG:={⟨M⟩|M isaTMand⟨M⟩̸∈L(M)}. ATM :={⟨M,w⟩|M isaTMandw∈L(M)}.
Theorem
DIAG ̸∈ SD.
ATM ∈SD\D.
DIAGc Definition
DIAGc := {⟨M⟩|M isaTMand⟨M⟩∈L(M)} {w | w does not encode a TM}.
Theorem
DIAGc ∈SD\D. Proof.
⟨M⟩ ∈ DIAGc ⇐⇒ ⟨M⟩ ∈ L(M) ⇐⇒ ⟨M,⟨M⟩⟩ ∈ ATM. Since ATM ∈ SD, it follows that DIAGc ∈ SD as well.
On the other hand DIAGc ̸∈ D, since otherwise DIAG ∈ D as D is closed under complementation.
A cT M Definition
AcTM := {⟨M,w⟩|M isaTMandw̸∈L(M)}
{w | w does not encode a pair of TM and input}.
Theorem
AcTM ̸∈SD. Proof.
We have already shown that ATM ∈ SD and D = SD ∩ coSD. If AcTM ∈ SD, then ATM ∈ coSD, and consequently, ATM ∈ D.
Reducibility
Definition
Let A, B be two languages. We say A is mapping reducible to B, written A ≤m B, if there is a computable function f : Σ∗ → Σ∗ such that for every w ∈ Σ∗,
w∈A ⇐⇒ f(w)∈B.
The function f is called the reduction from A to B.
Properties of reduction
Theorem (Properties of ≤m)
1. Reflexive: A ≤m A.
2. Transitive: If A ≤m B and B ≤m C, then A ≤m C.
3. IfA≤m B,thenAc ≤m Bc.
4. If A ≤m B and B is (semi-) decidable, then A is (semi-) decidable.
Proof.
1, 2 and 3 : Exercise!
Properties of reduction
4. Let MB be a (semi-) decider for B, let f be a reduction from A to B, and let Mf be a TM that computes f.
Consider the following TM MA: On input w:
Run Mf on w to obtain f(w).
Run MB on f(w) and output whatever MB outputs.
Asf isareductionfromAtoB,w∈A ⇐⇒ f(w)∈B. Equivalently, MB accepts f(w) iff w ∈ A.
Consequently, L(MA) = A, and hence, A is (semi-) decidable.
Corollary
If A ≤m B and A is not (semi-) decidable, then neither is B.
Application
Problem
Show that AcTM ̸∈ SD by reducing from DIAG. Proof.
Define f : Σ∗ → Σ∗ as follows:
f(⟨M⟩) = ⟨M,⟨M⟩⟩;
f(w) = ⟨Maccept,ε⟩ for strings w that do not encode a TM. (Maccept is a machine that always accepts.)
It is easy to see that f is computable.
Also, notice that
⟨M⟩ ∈ DIAG ⇐⇒ ⟨M⟩ ̸∈ L(M) ⇐⇒ ⟨M,⟨M⟩⟩ ∈ AcTM. (The reverse direction holds because ⟨Maccept, ε⟩ ̸∈ AcT M .)
Hence, DIAG ≤m AcTM.
Since DIAG ̸∈ SD, it follows that AcTM ̸∈ SD.