Notes - Computational Complexity HT25, Time and space

For all $x \in \Sigma^\ast$, $M$ runs in time $T( \vert x \vert )$.

(i.e. it halts within $T( \vert x \vert )$ steps).

For all $x \in \Sigma^\ast$, $M$ uses $S( \vert x \vert )$ space.

(i.e. it halts and uses at most $S( \vert x \vert )$ work tape cells, the input cells do not matter).

There exists a Turing machine that decides $L$ with time complexity $O(T)$.

There exists a Turing machine that decides $L$ with space complexity $O(T)$.

\[\mathsf P = \bigcup_{k \in \mathbb N} \mathsf{DTIME}(n^k)\]

\[E = \mathsf{DTIME}(2^{O(n)})\]

\[\mathsf{EXP} = \bigcup_{k \in \mathbb N} \mathsf{DTIME}(2^{n^k})\]

\[\mathsf{PSPACE} = \bigcup_{k \in \mathbb N} \mathsf{DSPACE}(n^k)\]

There exists another TM $M’$ that decides $L$ in $T’(n) = \frac{T(n)}{r} + n + 2$ steps.

Suppose:

• $f$ is a computable function

Then there exists time and space bounds $T$ and $S$ such that

\[\mathsf{DTIME}(T) = \mathsf{DTIME}(f(T))\]

and

\[\mathsf{DSPACE}(S) = \mathsf{DSPACE}(f(S))\]

There exists a TM $M$ which, on input $1^n$ outputs the binary representation of $T(n)$ in $O(T(n))$ time, or outputs the binary representation of $S(n)$ in $O(S(n))$ space.

Suppose:

• $T, T’ : \mathbb N \to \mathbb N$ are time bounds
• $T, T’$ are time constructible
• $T\log T = o(T’)$

Then:

\[\mathsf{DTIME}(T) \subsetneq \mathsf{DTIME}(T')\]

Let $\langle M \rangle$ denote the string representation of a TM, and define $\mu : \Sigma^\ast \to \{\text{TM}s\}$ which maps strings to Turing machines by:

\[\mu(x) = \begin{cases} M &\text{if } x \text{ is of the form } \langle M \rangle 01^i \text{ for some }i \\\\ \bot &\text{otherwise, where this is the TM that always halts} \end{cases}\]

Note that each Turing machine has infinitely many strings that map to it.

Consider the table with strings $s _ j$ as rows and Turing machines $M _ i := \mu(s _ i)$ as rows. Construct a Turing machine $D$ which on input $x _ i$ does the following:

• Read $x _ i$.
• Computes $T’( \vert x _ i \vert )$ (using the assumption $T’$ is time constructible)
• Compute $M _ i = \mu(x _ i)$.
• Run $\mathcal U$ on $\langle M _ i, x\rangle$ for at most $T’( \vert x _ i \vert )$ steps.
  • $\mathcal U$ is an “efficient enough” universal Turing machine
  • Since $T’$ is time constructible, $D$ can run in time $O(T’( \vert x _ i \vert ))$ by writing down $T’( \vert x _ i \vert )$ zeroes on a work tape and then erasing them for each step of the simulation by $\mathcal U$.
  • Since $T\log T = o(T’)$, if $M _ i$ terminates within $T( \vert x _ i \vert )$ steps, $\mathcal U$ can fully simulate $M _ i$ in $O(T’( \vert x _ i \vert ))$ steps.
• Two cases:
  • All zeroes are erased (“the clock runs out”): $D$ rejects.
  • $M _ i$ is simulated before zeroes are erased: $D$ outputs the opposite of $M _ i$.

By construction, $D$ runs in time $O(T’)$ and can diagonalise against all $O(T)$ Turing machines. Since we want to show that $\mathsf{DTIME}(T) \subsetneq \mathsf{DTIME}(T’)$, suppose that $L(D)$ could also be decided in $O(T)$ time. But then the encoding of this $O(T)$ Turing machine would appear as one of the rows. Then $D$ would disagree with this Turing machine on the diagonal, a contradiction.

(Since every Turing machine has infinitely many encodings, we can always pick $i$ large enough so that it is fully simulated with an arbitrarily large constant in the big-O notation).

Suppose:

• $S, S’ : \mathbb N \to \mathbb N$ are time bounds
• $S’$ is space constructible
• $S = o(s’)$

Then:

\[\mathsf{DSPACE}(S) \subsetneq \mathsf{DSPACE}(S')\]

There exists a universal Turing machine $\mathcal U$ such that if:

• $M$ is a Turing machine
• $M$ has time bound $t _ M$
• $M$ has space bound $s _ M(n)$
• $x$ is an input, $n = \vert x \vert $

Then:

• $\mathcal U$ uses $O( \vert \langle M \rangle \vert \cdot t _ M(n) \log t _ M(n))$ time simulating $M$ on $x$
• $\mathcal U$ uses $O( \vert \langle M \rangle \vert \cdot s _ M(n))$ space simulating $M$ on $x$

\[\mathsf{DTIME}(T) \subseteq \mathsf{DSPACE}(T)\]

Any computation halting in $T$ steps cannot use more than $T$ space.

\[\mathsf{DSPACE}(S) \subseteq \bigcup_{ c> 1} \mathsf{DTIME}(c^S)\]

Let $L$ be any language in $\mathsf{DSPACE}(S)$ and $M$ a Turing machine that decides $L$ in space $O(S)$.

Note that there are at most $(n+1)2^{O(S)}$ possible configurations of $M$ on any input of length $n$, since there are at most $(n+1)$ possible positions of the input tape head, at most $\text{poly}(S)$ positions of the work tape heads (there are a fixed number of tapes and each tape can have its tape head in any one of $S$ positions, so there are $\text{poly}(S)$ positions overall), at most $2^{O(S)}$ possible contents of the work tapes, and at most constantly many possible states of the machine.

Treat these configurations as a graph with edges between configurations. Implement BFS on the configuration graph, which takes time linear in the size of the configuration graph.

(note this proof also works for $\mathsf{NSPACE}$).