Separation of deterministic, nondeterministic and alternating complexity classes
type: Item
instance of: scholarly article
title: Separation of deterministic, nondeterministic and alternating complexity classes
zbMATH Open document ID: 0733.68029
DOI: 10.1016/0304-3975(91)90379-G
author: Andrej Bebják
author: Ivana Štefáneková
published in: Theoretical Computer Science
publication date: 1991-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 4213440
zbMATH Keywords: nondeterminism
zbMATH Keywords: alternation
zbMATH Keywords: lower bound
zbMATH Keywords: Turing machines
reviewed by: Juraj Hromkovič
MaRDI profile type: Publication
cites work: A time-space tradeoff for language recognition
cites work: One way multihead deterministic finite automata
cites work: On the power of alternation in automata theory
cites work: Q3725549
cites work: Q3048298
cites work: k + 1 Heads Are Better than k
full work available at URL: 0304-3975(91)90379-g
OpenAlex ID: W1981385397
description: scientific article; zbMATH DE number 4213440