Speed-up of Turing machines with one work tape and a two-way input tape. (English) Zbl 0631.68050
An alternating Turing machine (ATM) is called a \(\Sigma_ m-TM\) if for all inputs the computation tree of M starts with an existential state and alternates along each computation path at most m-1 times. It is shown that a deterministic Turing machine with one work tape and with time bound \(O(n^ 3)\) can be simulated by a \(\Sigma_ 2\)-TM of the same type with time bound \(O(n^ 2 \log^ 2n)\). This implies \(\Sigma_ 2TIME_ 1(n)\not\subseteq DTIME(n^{3/2}/\log^ 6n)\) and NTIME(n)\(\not\subseteq DTIME_ 1(n^{1.22})\).
Reviewer: M.Kratko
MSC:
68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
68Q25 | Analysis of algorithms and problem complexity |
03D10 | Turing machines and related notions |
03D15 | Complexity of computation (including implicit computational complexity) |