Logik in der Informatik
Prof. Dr. Martin Grohe

Institut für Informatik

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.

Zurück zur Vortragsübersicht 

Last modified: Mon Jan 23 10:23:22 CET 2006
André Hernich