Monday, November 27, 2017, 16.30
Seminar room 0.008, Mathematical Institute, University of Bonn
Speaker: Merlin Carl (Universität Konstanz)
Title: Complexity theory for ordinal Turing machines
Ordinal Turing Machines (OTMs) generalize Turing machines to transfinite working time and space. We consider analogues of theorems from complexity theory for OTMs, among them the Cook-Levin theorem, the P vs. NP problem and Ladner’s theorem. This is joint work with Benedikt Löwe and Benjamin Rin.