Separation of deterministic, nondeterministic and alternating complexity classes

DOI10.1016/0304-3975(91)90379-GzbMATH Open0733.68029OpenAlexW1981385397MaRDI QIDQ809596FDOQ809596

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• k + 1 Heads Are Better than k
• One way multihead deterministic finite automata
• On the power of alternation in automata theory
• A time-space tradeoff for language recognition

Cited In (12)

• Separation of the monotone NC hierarchy
• Circuit Definitions of Nondeterministic Complexity Classes
• Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
• Separating Complexity Classes Using Autoreducibility
• Separation of NP-completeness notions
• Title not available (Why is that?)
• Fine separation of average time complexity classes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

   Recommendations

• Title not available (Why is that?) 👍 👎
• Towards separating nondeterminism from determinism 👍 👎
• Alternating time versus deterministic time: A separation 👍 👎
• Title not available (Why is that?) 👍 👎
• Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines 👍 👎

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)