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

Review text

\textit{W. L. Ruzzo} [Tree-size bounded alternation, J. Comput. System Sci. 21, 218-235 (1980; Zbl 0445.68034)] introduced the notion of tree-size for alternating Turing machines (ATMs) and showed that it is a reasonable measure for classification of complexity classes. We establish that computations by tree-size and space simultaneously bounded ATMs roughly correspond to computations by time and space simultaneously bounded nondeterministic TMs (NTMs). We also show that not every polynomial time bounded and sublinear space simultaneously bounded NTM can be simulated by any deterministic TM with a slightly inceased time bound and a slightly decreased space bound simultaneously.

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

• 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
• Bandwidth contrained NP-complete problems
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• 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

(2)

• Deterministic versus nondeterministic space in terms of synchronized alternating machines
• Separation of deterministic, nondeterministic and alternating complexity classes

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)