7 Theorems on Complexity of Turing Machines
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)\)
(Only a draft): Build a 1 tape TM \(M'\) by introducing two symbols \(\triangleright '\) and \(\triangleleft '\) to denote the start and end of the \(k\)-th tape. Introduce \(\# \Sigma \) new symbols \(\overline{\sigma _i}\) to remember each tape’s head location. To generate the initial configuration \((q, \triangleright \triangleright ' x \triangleleft ' (\triangleright ' \triangleleft ' )^k )\), \(2k + \# \Sigma \) 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 \(\overline{\sigma _i}\) symbols, the second time write the new symbols. If a tape has to be extended, the \(\triangleleft '\) 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)\)
Parallel machines are polinomially faster than sequential machines.
Theorem. Linear speedup If \(I \in \mathrm{TIME}(f)\), then \(\forall \epsilon \in \mathbb {R}^+ . \ I \in \mathrm{TIME}(\epsilon \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 \(\epsilon \). The states of \(M'\) will be triples \([q,\sigma _{i_1},\hdots ,\sigma _{i_m},k]\) meaning the TM is in state \(q\) and has cursor on \(k\)-th symbol of \(\sigma _{i_1},\hdots ,\sigma _{i_m}\). \(M'\) then needs 6 steps to simulate \(m\) steps of \(M\). Therefore, \(M'\) will take \(\abs {x} + 2 + 6 \times \lceil \frac{f(\abs {x})}{m}\rceil \). Then \(m = \lceil \frac{6}{\epsilon } \rceil \). □
Same principle can apply to \(\mathrm{SPACE}\) with linear space compression. If \(I \in \mathrm{SPACE}(f(n))\), then \(\forall \epsilon \in \mathbb {R}^+ . \ I \in \mathrm{SPACE}(\epsilon \times f(n) + 2)\)
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\).
\(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 \(2f(\abs {x}) + \abs {x} + 1\) steps long.
Exponential loss in determinization, or bruteforce If \(I \in NTIME(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, \(\mathrm{NTIME}(f(n)) \subseteq \mathrm{TIME}(c^{f(n)})\)
Let \(d\) be the degree of nondeterminism of \(N\). \(\forall q \in Q, \sigma \in \Sigma \) sort \(\Delta (q,\sigma )\) 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)\downarrow \ \Leftrightarrow N(x)\downarrow \), also, all the possible simulations can be \(\O (d^{f(n) + 1})\).