+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +**********************************************************************
Zeit: Donnerstag, 24. Januar 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) Thema: Choiceless Computation and Logic
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 Dozenten der Informatik