Computer Science Graduate Seminar: Choiceless Computation and Logic

Thursday, January 24, 2019, 2:00pm

Location: Room 9222, Building E3, Ahornstr. 55

Speaker: Svenja Schalthöfer, M. Sc. (LuF Math. Grundlagen der Informatik, Lehrgebiet Informatik 7)


Choiceless computation emerged as an approach to the fundamental open question in descriptive complexity theory: Is there a logic capturing polynomial time? The main characteristic distinguishing logic from classical computation is isomorphism-invariance. Consequently, choiceless computation was developed as a notion of isomorphism-invariant computation that operates directly on mathematical structures, independently of their encoding. In particular, these computation models are choiceless in the sense that they cannot make arbitrary choices from a set of indistinguishable elements. Choiceless computation was originally introduced by Blass, Gurevich and Shelah in the form of Choiceless Polynomial Time (CPT), a model of computation using hereditarily finite sets of polynomial size as data structures.

We study the structure and expressive power of Choiceless Polynomial Time, the most promising candidate for a logic capturing polynomial time. Further, we expand the landscape of choiceless computation by a notion of Choiceless Logarithmic Space, which is, to our knowledge, the only candidate for a logic capturing logarithmic space.


The computer science lecturers invite interested people to join.