Separation of deterministic, nondeterministic and alternating complexity classes

DOI10.1016/0304-3975(91)90379-GMaRDI QIDQ809596zbMATH OpenOpenAlexFDO

Authors Andrej Bebják, Ivana Štefáneková

Publication date 1991

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(91)90379-g

zbMATH Keywords

alternationlower boundnondeterminismTuring machines

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

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.

Recommendations

• scientific article; zbMATH DE number 1222596
• Towards separating nondeterminism from determinism
• Alternating time versus deterministic time: A separation
• scientific article; zbMATH DE number 2102763
• Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines

Cites work

• k + 1 Heads Are Better than k
• A time-space tradeoff for language recognition
• scientific article; zbMATH DE number 3642749 (Why is no real title available?)
• scientific article; zbMATH DE number 3956444 (Why is no real title available?)
• On the power of alternation in automata theory
• One way multihead deterministic finite automata

Cited in

(17)

• Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
• Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines
• Separation of the monotone NC hierarchy
• Separation of NP-completeness notions
• scientific article; zbMATH DE number 4041256 (Why is no real title available?)
• scientific article; zbMATH DE number 4070311 (Why is no real title available?)
• scientific article; zbMATH DE number 4072383 (Why is no real title available?)
• scientific article; zbMATH DE number 4077187 (Why is no real title available?)
• scientific article; zbMATH DE number 4090800 (Why is no real title available?)
• Circuit Definitions of Nondeterministic Complexity Classes
• Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
• scientific article; zbMATH DE number 1143806 (Why is no real title available?)
• Fine separation of average time complexity classes
• Alternating time versus deterministic time: A separation
• scientific article; zbMATH DE number 4114605 (Why is no real title available?)
• scientific article; zbMATH DE number 2102763 (Why is no real title available?)
• Separating Complexity Classes Using Autoreducibility

This page was built for publication: Separation of deterministic, nondeterministic and alternating complexity classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q809596)