# Mitarbeiterseminar Logik in der Informatik

Freitag, 27. Januar 2006, 11:15 Uhr

RUD 25, Raum 4.410
## Reversal Complexity Revisited

André Hernich

Humboldt-Universität zu Berlin

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.