Merlin Carl: Complexity theory for ordinal Turing machines

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.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.