7 Theorems on Complexity of Turing Machines

Theorem

Reduction of tapes Let $M$ be a $k$ -tape TM, deciding $I$ in deterministic time $f$ , then $\exists$ a 1 tape TM $M^{'}$ that decides $I$ in time $\O (f^{2})$

Proof ▼

(Only a draft): Build a 1 tape TM $M^{'}$ by introducing two symbols $▹^{'}$ and $◃^{'}$ to denote the start and end of the $k$ -th tape. Introduce $# Σ$ new symbols $\overset{―}{σ_{i}}$ to remember each tape’s head location. To generate the initial configuration $(q, ▹ ▹^{'} x ◃^{'} (▹^{'} ◃^{'})^{k})$ , $2 k + # Σ$ states and $\O (\abs k)$ steps are needed. To simulate a move of $M$ , $M^{'}$ iterates the input datum from left to right, and back, 2 times: find the marked $\overset{―}{σ_{i}}$ symbols, the second time write the new symbols. If a tape has to be extended, the $◃^{'}$ parens have to be moved and a cascade happens. This takes $\O (f (\abs x))$ time, for each move of $M$ . Since $M$ takes $\O (f (\abs x))$ time to compute an answer, $M^{'}$ will take $\O (f (\abs x)^{2})$

Corollary

Parallel machines are polinomially faster than sequential machines.

Theorem. Linear speedup If $I \in TIME (f)$ , then $\forall ϵ \in R^{+} . I \in TIME (ϵ \times f (n) + n + 2)$ . Proof. (Draft): Build $M^{'}$ from $M$ solving $I$ , compacting $m$ symbols of $M$ into 1 of $M^{'}$ , in function of $ϵ$ . The states of $M^{'}$ will be triples $[q, σ_{i_{1}}, \hdots, σ_{i_{m}}, k]$ meaning the TM is in state $q$ and has cursor on $k$ -th symbol of $σ_{i_{1}}, \hdots, σ_{i_{m}}$ . $M^{'}$ then needs 6 steps to simulate $m$ steps of $M$ . Therefore, $M^{'}$ will take $\abs x + 2 + 6 \times ⌈ \frac{f (\abs x)}{m} ⌉$ . Then $m = ⌈ \frac{6}{ϵ} ⌉$ . □

Same principle can apply to $SPACE$ with linear space compression. If $I \in SPACE (f (n))$ , then $\forall ϵ \in R^{+} . I \in SPACE (ϵ \times f (n) + 2)$

Theorem

For each k-tape TM $M$ that decides I in deterministic time $f$ there exists an IO TM $M^{'}$ with k+2 tapes that computes I in time $c \times f$ for some constant $c$ .

Proof ▼

$M^{'}$ copies the first $M$ tape to the second tape, in $\abs x + 1$ steps. Then, $M^{'}$ operates identically to $M$ . If and when $M$ halts, $M^{'}$ copies the result to the tape $k + 2$ , in at most $f (\abs x)$ steps. $M^{'}$ computation was $2 f (\abs x) + \abs x + 1$ steps long.

Theorem

Exponential loss in determinization, or bruteforce If $I \in N T I M E (f (n))$ and is computed by $k$ -tape $N$ , it can also be computed by a deterministic TM $M$ with $k + 1$ tapes in time $\O (c^{f (n)})$ with an exponential loss of performance. In short, $NTIME (f (n)) \subseteq TIME (c^{f (n)})$

Proof ▼

Let $d$ be the degree of nondeterminism of $N$ . $\forall q \in Q, σ \in Σ$ sort $Δ (q, σ)$ lexicographically. Every computation of length $t$ carried by $N$ is a sequence of choices that can be seen as a sequence of natural numbers $(c_{1}, \hdots, c_{t})$ with $c_{i} \in [0. . d - 1]$ . The det. TM $M$ considers these successions in an increasing order, visiting the tree of nondeterministic computations, one at a time. Therefore $M (x) ↓ \Leftrightarrow N (x) ↓$ , also, all the possible simulations can be $\O (d^{f (n) + 1})$ . □