Reversal Complexity

DOI10.1137/0220039MaRDI QIDQ3978172zbMATH OpenOpenAlexFDO

Authors Jianer Chen, Chee K. Yap

Publication date 25 June 1992

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0220039

zbMATH Keywords

complete languagesparallel time complexityreversal hierarchiestape reduction theorem

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• The difference between one tape and two tapes: With respect to reversal complexity
• Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines
• A note on some simultaneous relations among time, space, and reversal for single work tape nondeterministic turing machines
• Sublogarithmic Bounds on Space and Reversals
• scientific article; zbMATH DE number 4007730

Cited in

(9)

• Transposition of an \(\ell \times \ell\) matrix requires \(\Omega\) (log \(\ell)\) reversals on conservative Turing machines
• On the relationship between deterministic time and deterministic reversal
• Tight lower bounds for query processing on streaming and external memory data
• Reverse complexity
• GENERALIZED COUNTERS AND REVERSAL COMPLEXITY
• Tradeoff lower lounds for stack machines
• A tradeoff theorem for space and reversal
• The difference between one tape and two tapes: With respect to reversal complexity
• Reversal complexity revisited

This page was built for publication: Reversal Complexity

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