Theory of Computation Review

This is a midterm review for CS6382 (syllabus)

Important problems

Topic 1: Determining decidability

Concepts

• r.e. = Turing-recognizable
• recursive = Turing-decidable
• A r.e. property $A$ is a language of TM codes such that every pair of TMs that generated the same language must either both inside or outside of $A$

Halting problem $⟨x,M⟩$, but fix $x$. Is this decidable?

Halting problem $⟨x,M⟩$, but fix $M$. Is this decidable?

Topic 2: “Characterization” of NP

Informally, the NP class is defined as the collection of languages that can be recognized by a Non-deterministic Turing Machine (NTM) in polynomial time.

To precisely define “polynomial time”, and “can be recognized”, we come to the following definition. $A\in NP\iff \mathrm{\exists }B\in P,\text{polynomial }p:\mathrm{\forall }x,|x|=n,x\in A\iff (\mathrm{\exists }y,|y|\le p(n))[⟨x,y⟩\in B]$

Human language: $A$ is a language in NP if and only if

• there eixsts
  • another language $B$ in $P$
  • a polynomial $p$
• such that:
  • for any string $x$ with length $n$:
    • $x$ belongs to $A$ if and only if:
      • there exits a string $y$
      • such that:
        • length of $y$ does not exceed $p(n)$
        • the concatenation $⟨x,y⟩$ belongs to $B$.

With that, $p()$ and the fact that $B\in P$ formalizes the notion of polynomial time. The running of the NTM is translated to the existence of a polynomial length string $y$ (representing the running path of the NTM). $y$ and the language $B$ is the representation of the NTM.

In some cases, we restrict the alphabet for $y$ to be $\{0,1\}$.

Topic 3: Using Partition and Subsum to prove NP-completeness

Concepts

The following two problems are NP-complete:

• Partition: Given a set of positive intergers $A$. Check if there exists a partition $A_1\cap A_2=2$ (disjoint) such that Sum($A_1$) = Sum($A_2$).
• Subsum: Given a set of positive intergers $A$. Check if there exists a subset $B\subset A$ such that Sum($A$) = $S$.

To prove a problem $A$ is NP-hard, we “reduce” an NP-hard problem $B$ to $A$. May have to turn $A$ to a decision version. Depending on the reduction specified, we have a corresponding method:

• If using many-to-one reduction, we need to (1)construct a polynomial-time many-to-one reduction algorithm to reduce the input $y$ of $B$ to the input $x$ of $A$, then prove that (2) $y\in B\Rightarrow x\in A$ and (3) the converse.
• If using Turing reduction, we need to construct a polynomial-time DTM with oracle A that accepts B.

Topic 4: Using Turing-reduction to prove a completeness in Polynomial Hierarchy

Concepts

• More about Turing reduction:
  • rather than changing the input to another one in many-one reduction, we use the original input, but consulting an oracle in the TM.
  • It is transitive.
  • Notations for $A{\le }_T^{p}B$
    • $A\in P(B)$,
    • or $A\in P^B$.
  • It is a “weaker” reduction than many-to-one.
  • It should not be merged naively with many-to-one.
• Polynomial Hierarchy (PH) arises from this:
  • The hierachy starts with ${\mathrm{\Sigma }}_0^p={\mathrm{\Pi }}_0^p={\mathrm{\Delta }}_0^p=P$
  • Then built by: ${\mathrm{\Sigma }}_{n+1}^p=P({\mathrm{\Sigma }}_n^p),{\mathrm{\Pi }}_{n+1}^p=NP({\mathrm{\Sigma }}_n^p),{\mathrm{\Delta }}_{n+1}^p=co-NP({\mathrm{\Sigma }}_n^p)$
    • Level 1: ${\mathrm{\Sigma }}_1^p=NP(P)=NP;{\mathrm{\Delta }}_1^p=co-NP(P)=co-NP(P);{\mathrm{\Pi }}_1^p=P(P)=P$
    • Level 2: ${\mathrm{\Delta }}_2^p=P(NP)$ …
  • Finally, $PH={\cup }_n{\mathrm{\Sigma }}_n^p$

Example: Prove that Exact-Clique is ${\le }_T^p$-complete in ${\mathrm{\Delta }}_2^p$

Proof:

• We have Exact-Clique ${\le }_T^p$ Clique $\Rightarrow$ Exact-Clique $\in P(NP)={\mathrm{\Delta }}_2^p$
• Every problem in ${\mathrm{\Delta }}_2^p$ can be Turing-reduced to some problem in $NP$, which can be many-one-reduced to Clique, which can be Turing-reduced to Exact-Clique (q.e.d.)

Topic 5: Proving Space Bounded Halting Problem is PSPACE-complete

Problem. SBHP = “Given an DTM M, an input x and a string $0^s$, can M accept x using space at most s?” Prove that SBHP is PSPACE-complete by many-one reduction.

Proof.

• Language form: $L=\{⟨m,x,0^s⟩|M\text{ accepts }x\text{ within space }s\}$
• First, prove it belongs to PSPACE by the existence of the universal TM.
• p-m reduction: From a string y in A, construct the input $⟨M,y,0^{p(|y|)}⟩$ for $L$. We have $A\in PSPACE\iff ⟨M,y,o^{p(|y|)}⟩\in L$. Therefore, we have reduced all problem in PSPACE to $L$.

Miscelaneous

“The barber that cuts his own hair”

• Diagionalization technique is very intersting. Used to prove something is non-countable by contradiction.
• Halting problem is one of those. The language version: $\{M|M\text{ accepts }code(M)\}$
  • Method 1: See the textbook
  • Method 2: Still cooking it …
  • In class, my prof used the barber paradox to illustrate. I was in fact inspired by this technique to cut my actual hair.