Separation of deterministic, nondeterministic and alternating complexity classes (Q809596)

The paper deals with some classical questions like whether nondeterminism is more powerful than determinism, or whether alternation is more powerful than nondeterminism. Modifying the lower bound techniques from \textit{\`P. Ďuriš}, and \textit{Z. Galil} [Math. Syst. Theory 17, 3-12 (1984; Zbl 0533.68047)] and \textit{J. Hromkovič} [Theor. Comput. Sci. 67, 99-110 (1989; Zbl 0679.68085)] it is shown that alternating (nondeterministic) off-line Turing machines working in \(TIME\times SPACE=0(n \log n)\) accept a language which cannot be accepted by any nondeterministic (deterministic) off-line Turing machine working in \(TIME\times SPACE=0(n^ 2)\). These results are extended also for off- line Turing machines with several heads on the input tape. Finally, some low hierarchies for TIME\(\times SPACE\) deterministic (nondeterministic) complexity classes, and for TIME\(\times SPACE\times PARALLELISM\) alternating complexity classes are established.