Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines

DOI10.1007/BF01179374MaRDI QIDQ1323339zbMATH OpenOpenAlexFDO

Authors Shigeki Iwata, Takumi Kasai, Etsuro Moriya

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 classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Speed-Up of Turing Machines with One Work Tape and a Two-Way Input Tape
• Separation of deterministic, nondeterministic and alternating complexity classes
• A note on some simultaneous relations among time, space, and reversal for single work tape nondeterministic turing machines
• On reversal bounded alternating Turing machines
• scientific article; zbMATH DE number 3917711

Cites work

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

Cited in

(1)

• Deterministic versus nondeterministic space in terms of synchronized alternating machines

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

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