(Swansea)

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.Board Room

Department of Computer Science