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

lower boundnondeterminismTuring machinesalternation

Mathematics Subject Classification ID

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

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

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

Cited in

(14)

• 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
• scientific article; zbMATH DE number 1143806 (Why is no real title available?)
• scientific article; zbMATH DE number 4041256 (Why is no real title available?)
• scientific article; zbMATH DE number 4072383 (Why is no real title available?)
• Fine separation of average time complexity classes
• Circuit Definitions of Nondeterministic Complexity Classes
• Separation of NP-completeness notions
• Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
• scientific article; zbMATH DE number 4070311 (Why is no real title available?)
• Separation of the monotone NC hierarchy
• scientific article; zbMATH DE number 4077187 (Why is no real title available?)
• scientific article; zbMATH DE number 4090800 (Why is no real title available?)

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)