Computational Complexity HT25, Time and space

Created: January 26, 2025 | Updated: June 01, 2025 | About these notes | View in context | Study these flashcards

Flashcards

Basic definitions

Suppose:

  • $M$ is a Turing machine
  • $T : \mathbb N \to \mathbb N$

@Define what it means for $M$ to have time complexity $T$.

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

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

Suppose:

  • $M$ is a Turing machine
  • $S : \mathbb N \to \mathbb N$

@Define what it means for $M$ to have space complexity $S$.

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).

Suppose:

  • $L$ is a language
  • $T : \mathbb N \to \mathbb N$

@Define what it means for $L \in \mathsf{DTIME}(T)$.

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

Suppose:

  • $L$ is a language
  • $T : \mathbb N \to \mathbb N$

@Define what it means for $L \in \mathsf{DSPACE}(T)$.

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

Suppose:

  • $T : \mathbb N \to \mathbb N$ is a time bound
  • $S : \mathbb N \to \mathbb N$ is a space bound

@Define what it means for $T$ to be time constructible and $S$ to be space constructible.

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.

@Define a configuration of a $k$-tape TM $M$, and count how many there are for a

A tuple $(q, p _ i, p _ 1, \ldots, p _ k, \gamma _ 1, \ldots, \gamma _ k)$ where:

  • $q \in Q$ is the current state
  • $p _ i$ is the position of the tape head on the input tape
  • $p _ 1, \ldots, p _ k$ are the positions of the tape heads on the other $k$ tapes
  • $\gamma _ 1, \ldots, \gamma _ k$ are the contents of the tapes

Assuming that $M$ uses space $S$, there are

\[O((n+1) \cdot \text{poly}(S(n)) \cdot 2^{O(S(n))})\]

since there are $n+1$ possible locations for the input pointer on the input tape, $\text{poly}(S(n))$ possible locations for the other tape heads, and then $2^{O(S(n))}$ possible contents of the other work tape.

Classes

@Define the class $\mathsf P$.
\[\mathsf P = \bigcup_{k \in \mathbb N} \mathsf{DTIME}(n^k)\]

@Define the class $\mathsf E$.
\[E = \mathsf{DTIME}(2^{O(n)})\]

@Define the class $\mathsf{EXP}$.
\[\mathsf{EXP} = \bigcup_{k \in \mathbb N} \mathsf{DTIME}(2^{n^k})\]

@Define the class $\mathsf{PSPACE}$.
\[\mathsf{PSPACE} = \bigcup_{k \in \mathbb N} \mathsf{DSPACE}(n^k)\]

Speedup theorem

Suppose:

  • $T : \mathbb N \to \mathbb N$ is a time function/bound
  • $r \in \mathbb N$
  • $M$ decides a language $L$ in $T$ steps

In this context, @state the speedup theorem.

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

@Prove the speedup theorem, i.e. that if

  • $T : \mathbb N \to \mathbb N$ is a time function/bound
  • $r \in \mathbb N$
  • $M$ decides a language $L$ in $T$ steps

Then:

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

Encode $k$-tuples of symbols of $M$ as single symbols of $M’$, by increasing the alphabet of $M’$ to $\Gamma^k$.

Compress the input of $M$ of length $n$ to a new string of length $n/k$. To copy over $n$ inputs from $M$ to $M’$, we need $n + n/k + 2$ steps: $n$ steps to read, $n/k$ steps to write and $2$ steps to bring the pointers both back to the left (?).

Once the input has been copied, simulate $k$ steps in $M$ with $M’$; note only $4$ steps are required in $M’$ to cover any radius of $k$ steps in $M$. If $M$ moves $L$ or $R$, we can simulate this in $2$ steps. This makes a total of $6$ steps, so the simulation phase needs at most $6T / k$ steps. Set $k = 6r$, and we are done.

Gap theorem

@State the gap theorem informally.

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))\]

Hierarchy theorems

See [[Notes - Computational Complexity HT25, Hierarchy theorems]]U.

Relationship between time and space

Suppose:

  • $T$ is a time bound

@State and @justify a relationship between $\mathsf{DTIME}(T)$ and $\mathsf{DSPACE}(T)$.
\[\mathsf{DTIME}(T) \subseteq \mathsf{DSPACE}(T)\]

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

Suppose:

  • $S$ is a space-constructible bound
  • $S = \Omega(\log n)$

@State an upper bound on $\mathsf{DSPACE}$ in terms of $\mathsf{DTIME}$ in this context.
\[\mathsf{DSPACE}(S) \subseteq \mathsf{DTIME}(2^{O(S)})\]

Suppose:

  • $S$ is a space-constructible bound
  • $S = \Omega(\log n)$

@Prove that then:

\[\mathsf{DSPACE}(S) \subseteq \mathsf{DTIME}(2^{O(S)})\]

(the same proof also shows that $\mathsf{NSPACE}(S) \subseteq \mathsf{DTIME}(2^{O(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) \cdot \text{poly}(S(n)) \cdot 2^{O(S(n))}$ 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), and
  • 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.

(you can suppress the $\text{poly}(S(n))$ factor in the big-O notation, and if $S(n) = \Omega(\log n)$, you can also suppress the note this proof also works for $\mathsf{NSPACE}$).



Related posts