A relation between space, return and dual return complexities

We introduce the dual return complexity and prove that the return complexity classes and the dual return complexity classes of nondeterministic Turing machines coincide with the tape complexity classes of Turing machines with auxiliary pushdown tape for resource functions ƒ⩾id, id being the identity function.

Authors

• Gerd Wechsung
• Andreas Brandstädt

Keywords

No keywords are indexed for this paper.