Alternating time versus deterministic time: A separation

DOI10.1007/BF01301970zbMath0868.68053OpenAlexW2104933102MaRDI QIDQ4717057

No author found.

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

Related Items (1)

Time-space tradeoffs for SAT on nonuniform machines

Cites Work

• Unnamed Item
• A Turing machine time hierarchy
• On proving time constructibility of functions
• Speedups of deterministic machines by synchronous parallel machines
• The method of forced enumeration for nondeterministic automata
• On alternation
• On alternation. II. A graph theoretic approach to determinism versus nondeterminism
• A hierarchy for nondeterministic time complexity
• Time- and tape-bounded Turing acceptors and AFLs
• Nondeterministic Space is Closed under Complementation
• Alternation
• On Time Versus Space
• Separating Nondeterministic Time Complexity Classes
• On the Computational Complexity of Algorithms

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