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

Abstract:

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.