Allgemeines

Veranstaltungsnummer  
Veranstalter Thomas Zeume
Klassifikation Seminar
Semester Sommersemester 2019
Ort und Zeit  
Vorbesprechung 28.02.2019, 14:00 Uhr, OH12-3.013
(eine spätere Themenvergabe ist nach Absprache möglich)
Kontakt Diese E-Mail-Adresse ist vor Spambots geschützt! Zur Anzeige muss JavaScript eingeschaltet sein!

Inhalt

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.

Da die einzelnen Themen aus sehr unterschiedlichen Gebieten stammen, soll jeder Vortrag zunächst eine breite Einführung in das Gebiet geben, bevor dann die konkrete Fragestellung vertieft wird. Die Vorträge sollen deshalb wie eine 90-minütige Vorlesung konzipiert werden, ähnlich dem Stil der Vorlesung Konzepte und Methoden der theoretischen Informatik. Die Seminararbeit soll als dazugehöriges Skript im Umfang von 8-10 Seiten konzipiert sein.

Bei grundsätzlichem Interesse an diesem Seminar würde ich mich über eine kurze Nachricht freuen!

Themenvorschläge

Weitere Themen sind nach Rücksprache möglich.

Grenzen in Logik und Berechenbarkeit
  • An der Grenze zwischen Entscheidbarkeit und Unentscheidbarkeit
    • Klassische Fragmente der Prädikatenlogik
      • Verschiedene Themen möglich
      • 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
      • Möglicher Startpunkt: 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.
  • 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
    • Weitere Themen, beispielsweise aus Stasys Jukna: Boolean Function Complexity sind möglich
    • 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 Isolationslemma
    • 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).
  • Probabilistische Automaten
    • Möglicher Startpunkt: Fijalkow, Nathanaël. "Undecidability results for probabilistic automata." ACM SIGLOG News 4.4 (2017): 10-17.