Informatik-Oberseminar: Choiceless Computation and Logic

Donnerstag, 24.01.2019, 14.00 Uhr

Ort: Raum 9222, Gebäude E3, Ahornstr. 55

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

Abstract:

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.

 

Es laden ein: Die Dozentinnen und Dozenten der Informatik