35th Multi-dimension Seminar
Polynomial Time Computation on Sets
Prof. Arnold Beckmann

Swansea University, Department of Computer Science, Wales, UK

2011-08-04 (Thu.), 15:00-16:30

KS-Lecture Room 3, 4

Polynomial time computation on finite strings is a central notion in complexity theory. Polynomial time on infinite strings has been considered by several authors in the context of infinite time Turing machines. In this talk we will discuss how polynomial time computation can be defined on sets in general. Our approach is based on the Bellantoni-Cook schemes characterising polynomial time on finite strings in terms of "safe recursion". In particular we will analyse what complexity class on finite strings arise under various interpretations of finite strings as sets. For one natural such interpretation the class obtained can be characterised as alternating exponential time with polynomially-many alternations. A similar class has been considered before as the complexity of the theory of the real numbers as an ordered additive group. This is joint work with Sam Buss and Sy Friedman.

Contact Person

Norbert Preining