Notes - Computational Complexity HT25, Turing reductions

Created: January 26, 2025
Updated: February 13, 2025

Flashcards

Informally, what is an oracle Turing machine and how is oracle access for $L$ used?
  • An oracle Turing machine has a write-only oracle tape in addition to its input tape and work tapes
  • The TM can write a string $x$ to the oracle tape and then move into a query state $q _ ?$
  • Then the TM either enters state $q _ \text{yes}$ or $q _ \text{no}$ depending on whether $x \in L$.

Suppose:

  • $L _ 1, L _ 2$ are recursively enumerable languages
  • $M$ is a TM with language $L _ 2$

@Define what it means for $L _ 1$ to Turing reduce to $L _ 2$, i.e. $L _ 1 \le _ T L _ 2$.

We can construct an oracle Turing machine $M’$ which solves $L _ 1$ using an oracle for $L _ 2$.

Suppose:

  • $L _ 1, L _ 2$ are recursively enumerable languages
  • $L _ 1 \le _ T L _ 2$

@State a result about decidability in this context.

If $L _ 2$ is decidable, then $L _ 1$ is decidable.

Give an @example to show that the property of being recursively enumerable is not preserved under Turing reducibility.
  • $\overline{\mathsf{Accept _ TM} }$ is not RE (since if both this and $\mathsf{Accept _ TM}$ were then $\mathsf{Accept _ {TM} }$ would be decidable, which it is not).
  • But $\overline{\mathsf{Accept _ TM} } \le _ T \mathsf{Accept _ {TM} }$ (since given an oracle to $\mathsf{Accept _ TM}$, just ask for membership and then take the complement).

Suppose:

  • $L _ 1, L _ 2$ are recursively enumerable languages
  • $M$ is a TM with language $L _ 2$

@Define what it means for $L _ 1$ to Turing reduce to $L _ 2$, i.e. $L _ 1 \le _ T^\text{poly} L _ 2$.

We can construct an oracle Turing machine $M’$ which solves $L _ 1$ in polynomial time using an oracle for $L _ 2$.

@Justify why $\mathsf{UNSAT} \le _ T^\text{poly} \mathsf{SAT}$.

A Turing machine with oracle access to $\mathsf{SAT}$ can ask whether $x \in \mathsf{SAT}$ and output the opposite answer.

@Justify why if $L’ \le _ T^\text{poly} L$ and $L \in \mathsf P$, then $L’ \in \mathsf P$.

If a Turing machine for $L’$ uses an oracle for a language in $\mathsf P$ polynomially many times, it might as well just compute membership itself in polynomial time. Since polynomials are closed under composition, it follows $L’ \in \mathsf P$.



Related posts