# CS代考计算机代写 flex Computational Complexity and Computability

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 ∈SDD.

DIAGc Definition

DIAGc := {⟨M⟩|M isaTMand⟨M⟩∈L(M)} {w | w does not encode a TM}.

Theorem

DIAGc ∈SDD. 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.