|
|
Deskriptive Komplexität und endliche Modelltheorie (KomMod)- Dozent/in
- Dr. Wolfgang Degen
- Angaben
- Vorlesung
4 SWS, Schein, benoteter Schein, ECTS-Studium, ECTS-Credits: 8
Zeit und Ort: Do 9:00 - 10:00, 0.111; Di 14:30 - 16:30, 0.141; Bemerkung zu Zeit und Ort: Die Räume 0.111 und 0.141 befinden sich in der Cauerstr. 6
Vorbesprechung: 16.10.2006, 14:15 - 15:00 Uhr, Raum 0.141
- Inhalt
- In der klassischen Komplexitätstheorie definiert und studiert man Komplexitätsklassen wie P, NP, PSPACE, etc. in Bezug auf die Ressourcen von Turing-Maschinen. In den beiden letzten Dekaden hat sich jedoch auch ein l o g i s c h e r Zugang zu diesen Klassen entwickelt, der darin besteht, daß Problem-Instanzen als endliche Modelle logischer Sätze aufgefasst werden. Auf diese Weise ist es gelungen, ganze Komplexitätsklassen durch gewisse Logiken "einzufangen".
In der Vorlesung wird auch die Metatheorie der einschlägigen Logiken behandelt werden.
- Empfohlene Literatur
- Ch. H. Papadimitriou: Computational Complexity, Addison-Wesley, 1994
H.-D. Ebbinghaus, J. Flum: Finite Model Theory, Springer, 19992
N. Immerman, Ph.G. Koalitis (Eds.): Descriptive Complexity and Finite Models, AMS, 1997
N. Immerman: Descriptive Complexity, Springer, 1999
- ECTS-Informationen:
- Title:
- Descriptive Complexity and Finite Model Theory
- Credits: 8
- Contents
- In Classical Complexity Theory one defines as studies complexity classes like P, NP, PSPACE, etc. with respect to the resources of Turing machines. However, during the last two decades one has developed also a l o g i c a l approach to those classes, which consists in considering problem instances as finite models of logical sentences. In this way, whole complexity classes are "captured" by certain logics. In the lecture we also treat the metatheory of the pertinent logics.
- Literature
- Ch. H. Papadimitriou: Computational Complexity, Addison-Wesley, 1994
H.-D. Ebbinghaus, J. Flum: Finite Model Theory, Springer, 1995N.
Immerman, Ph.G. Koalitis (Eds.): Descriptive Complexity and Finite Models, AMS, 1997
N. Immerman: Descriptive Complexity, Springer, 1999
- Zusätzliche Informationen
- Erwartete Teilnehmerzahl: 10
- Institution: Lehrstuhl für Informatik 10 (Systemsimulation)
|
 |
|
|
UnivIS ist ein Produkt der Config eG, Buckenhof |
|
|