×

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)
Full Text: DOI