Wo verläuft die Grenze zwischen Entscheidbarkeit und Unentscheidbarkeit? Welche Probleme lassen sich mit moderatem Ressourcenbedarf lösen? Wo liegen die Grenzen unserer Methoden für den Nachweis von unteren Schranken an den Ressourcenbedarf von Problemen? Was lässt sich überhaupt beweisen?
In diesem Seminar wollen wir theoretische Grenzen aus verschiedensten Bereichen der theoretischen Informatik ausloten. Dabei soll der Fokus auf Grenzen aus der Logik, Komplexitäts- und Berechenbarkeitstheorie, sowie aus der Automatentheorie liegen. Eine mögliche Liste von Themen ist unten aufgeführt. Die Vorstellung anderer Themen ist nach Absprache möglich.
Mögliche Themen
Grenzen in Logik und Berechenbarkeit
- An der Grenze zwischen Entscheidbarkeit vs. Unentscheidbarkeit
- Klassische Fragmente der Prädikatenlogik
- Möglicher Startpunkt: Börger, Grädel, Gurevich: The Classical Decision Problem.
- Das Guarded Negation-Fragment
- Möglicher Startpunkt: Bárány, Vince, Balder Ten Cate, and Luc Segoufin. "Guarded negation." Journal of the ACM (JACM) 62.3 (2015): 22.
- Das separierte Fragment
- Sturm, Thomas, Marco Voigt, and Christoph Weidenbach. "Deciding First-Order Satisfiability when Universal and Existential Variables are Separated." Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science. ACM, 2016.
- Presburger Arithmetik
- Christoph Haase: A survival guide to presburger arithmetic. ACM SIGLOG News 5(3): 67-82 (2018)
- Gödels Unvollständigkeitssätze
Mögliche Startpunkte:
Hoffmann: Grenzen der Mathematik. Kapitel 4
Ebbinghaus, Flum, Thomas: Einführung in die mathematische Logik. Kapitel X
- Hilberts 10. Problem
- Möglicher Startpunkt: Schöning, Pruim: Gems of Theoretical Computer Science. Kapitel 2
- Unvergleichbare, unentscheidbare Probleme: Die Priorisierungsmethode von Muchnik und Friedberg
- Möglicher Startpunkt: Schöning, Pruim: Gems of Theoretical Computer Science. Kapitel 1
Grenzen in der Komplexitätstheorie
- Grenzen von Beweismethoden: Natürliche Beweise
- Möglicher Startpunkt: Arora, Barak: Computational Complexity - A Modern Approach. Kapitel 23.
- Untere Schranken für Schaltkreise
- Untere Schranken für AC0: Die Methode von Razborov
- Möglicher Startpunkt: Stasys Jukna: Boolean Function Complexity. Kapitel 12.1-12.3
- Untere Schranken für AC0[p]: Die Methode von Smolensky
- Möglicher Startpunkt: Stasys Jukna: Boolean Function Complexity. Kapitel 12.5
- Untere Schranken für ACC: Die Methode von Williams
- Möglicher Startpunkt: Williams, Ryan. "Nonuniform ACC circuit lower bounds." Journal of the ACM (JACM). 2014.
- Nicht-Determinismus vs. Eindeutigkeit von Berechnungspfaden: Das Isolation Lemma
- Möglicher Startpunkt: Klaus Reinhardt, Eric Allender: Making Nondeterminism Unambiguous. SIAM J. Comput. 29(4): 1118-1131 (2000)
- Untere Schranken für Dynamische Algorithmen
- Möglicher Startpunkt: Patrascu, Mihai, and Erik D. Demaine. "Logarithmic lower bounds in the cell-probe model." SIAM Journal on Computing. 2006.
- Zeit-Platz Trade-offs mit Hilfe von Pebble-Spielen
- Möglicher Startpunkt: Gems of Theoretical Computer Science, Chapters 23. Superconcentrators and the Marriage Theorem and 24. The Pebble Game
An der Grenze von Logik und Komplexität
- Meta-Theoreme
- Meta-Theoreme für die Prädikatenlogik
- Möglicher Startpunkt: Grohe, M., Kreutzer, S.: Methods for algorithmic meta theorems. In: Grohe, M., Makowsky, J. (eds.) Model Theoretic Methods in Finite Combinatorics, Contemporary Mathematics, vol. 558, pp. 181–206. American Mathematical Society (2011)
- Meta-Theorem für die Approximierbarkeit
- Möglicher Startpunkt: Papadimitriou, C., Yannakakis, M.: Optimization, approximation, and complexity classes. Journal of Computer and System Sciences 43, 425–440 (1991)
- Komplexität des Constraint Satisfaction Problems
- Möglicher Startpunkt: Martin Grohe: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54(1): 1:1-1:24 (2007)
Grenzen in der Automatentheorie
Komplexität der Erreichbarkeit in Petrinetzen
Möglicher Startpunkt: Czerwinski, Wojciech, et al. "The Reachability Problem for Petri Nets is Not Elementary." arXiv preprint arXiv:1809.07115 (2018).
- Kursleiter/in: Thomas Zeume