Computational Complexity HT25, Diagonalisation
Diagonalisation is one of the few techniques we have for proving unconditional lower bounds on complexity classes.
Flashcards
The halting problem
@Prove that the language
\[L :=\mathsf{Accept_{TM} } = \\{\langle M, x \rangle : M \text{ accepts }x\\}\]
is recursively enumerable but not decidable via a diagonalisation argument.
$L$ is recursively enumerable since to decide membership we can just use a universal Turing machine to simulate $M$ on $x$.
But suppose that it is also decidable.
Construct a table $A$ where the rows are encodings of Turing machines and the columns are all possible strings. Set $A[i, j] = 1$ if and only if $M _ i$ accepts $s _ j$.
Construct a new language by flipping the diagonal, i.e. $s _ i \in L’ \iff \langle M _ i, s _ i \rangle \notin L$.
If $L$ is decidable, then $L’$ is also decidable. But if $L’$ is decidable, then there exist some Turing machine $M _ i$ that appears among the rows of the table. This leads to a contradiction, since this Turing machine would have to accept $s _ i$, but by definition it doesn’t.
Hence $L$ cannot be decidable.
Time and space hierarchy theorems
See [[Notes - Computational Complexity HT25, Hierarchy theorems]]U.
Other examples
Given a language $L \subseteq \lbrace 0, 1 \rbrace^\ast$, define the census function
\[\begin{aligned}
&\text{cens}_L : \lbrace 1 \rbrace^\ast \to \mathbb N \\\\
&\text{cens}_L(1^n) = |L \cap \lbrace 0, 1 \rbrace^n|
\end{aligned}\]
@Prove that there is a language $L \in \mathsf{DTIME}(2^n)$ such that $\text{cens} _ L$ is not computable in time $O(2^{n/2})$.
The idea is to use diagonalisation. Let $M _ 1, M _ 2, \ldots$ be an enumeration of the Turing machines such that each Turing machine occurs infinitely many times, and where these Turing machines compute corresponding functions $f _ 1, \ldots, f _ n$.
We want to find some $M$ such that $\text{cens} _ {L(M)}$ is not computed by any $M _ i$ with runtime $O(2^{n/2})$ where $M$ runs in time $O(2^n)$.
- On input $x$:
- Calculate the corresponding TM $M _ i$
- Run $M _ i$ on $x$ of length $n$ for up to $2^n$ steps. If $M _ n$ halts and outputs an integer $z > 0$, $M$ rejects, otherwise it accepts.
@example~ @exam~