Alternating time versus deterministic time: A separation

DOI10.1007/BF01301970MaRDI QIDQ4717057zbMATH OpenOpenAlexFDO

Authors

Publication date 17 August 1997

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01301970

zbMATH Keywords

deterministic Turing machines

Mathematics Subject Classification ID

Recommendations

• scientific article; zbMATH DE number 2102763
• scientific article; zbMATH DE number 1222596
• Towards separating nondeterminism from determinism
• Speed-Up of Turing Machines with One Work Tape and a Two-Way Input Tape
• Separation of deterministic, nondeterministic and alternating complexity classes

Cites work

• A hierarchy for nondeterministic time complexity
• A Turing machine time hierarchy
• Alternation
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• Nondeterministic Space is Closed under Complementation
• On alternation
• On alternation. II. A graph theoretic approach to determinism versus nondeterminism
• On proving time constructibility of functions
• On the Computational Complexity of Algorithms
• On Time Versus Space
• Separating Nondeterministic Time Complexity Classes
• Speedups of deterministic machines by synchronous parallel machines
• The method of forced enumeration for nondeterministic automata
• Time- and tape-bounded Turing acceptors and AFLs

Cited in

(5)

• A note on parallel and alternating time
• Speed-Up of Turing Machines with One Work Tape and a Two-Way Input Tape
• scientific article; zbMATH DE number 2102763 (Why is no real title available?)
• Time-space tradeoffs for SAT on nonuniform machines
• Separation of deterministic, nondeterministic and alternating complexity classes

This page was built for publication: Alternating time versus deterministic time: A separation

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