Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines

DOI10.1007/BF01179374zbMath0790.68044OpenAlexW2008300589MaRDI QIDQ1323339

Etsuro Moriya, Shigeki Iwata, Takumi Kasai

Publication date: 1993

Published in: Acta Informatica (Search for Journal in Brave)

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

zbMATH Keywords

alternating Turing machinesmeasure for classification of complexity classes

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Tree-size bounded alternation
• On uniform circuit complexity
• On time-space classes and their relation to the theory of real addition
• Bandwidth contrained NP-complete problems
• Towards separating nondeterminism from determinism
• A note on some simultaneous relations among time, space, and reversal for single work tape nondeterministic turing machines
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• Separating Nondeterministic Time Complexity Classes
• Relations Among Complexity Measures
• Real-time solutions of the origin-crossing problem

This page was built for publication: Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines