Logik in der Informatik Prof. Dr. Martin Grohe

Institut für Informatik

Reversal Complexity Revisited

We look at complexity classes based on Turing machines with several "external memory tapes" on which the number of head reversals is bounded by r(n), and further "internal memory tapes" on which space is bounded by s(n). Recently, such machines were introduced as a computational model which restricts the number of random accesses to external memory, and the size of internal memory. First, we address correspondences between these complexity classes and time, space, and reversal complexity classes. For example, we will see that we do not need internal space s(n) if we are willing to add an extra factor s(n) to the number of head reversals on external memory tapes, and we obtain characterisations of nondeterministic time and polylogarithmic space. Second, we address their structural complexity: we will see that these classes form hierarchies in terms of increasing numbers of head-reversals.