Studien- und Abschlussarbeiten

Go ist ein 2-Spieler Strategiespiel, welches auf einem 19x19 Brett gespielt wird. 1983 wurde bewiesen, dass die Komplexität von (verallgemeinertem) Go - also die Frage, ob Schwarz von einer gegebenen Position einen Sieg erzwingen kann - EXPTIME vollständig ist. Der Beweis dafür, welcher sich durch mehrere Papers zieht, soll nachvollzogen und präsentiert werden. Das genannte Resultat gilt nur für eine bestimmte Variante des Spiels. (Ohne die sogenannte "Superko-Regel".) Diese Einschränkung soll erklärt werden und es soll untersucht werden, ob sich diese Lücke schließen lässt. Dieses Thema ist vorrangig für eine Masterarbeit geeignet.

In der Kommunikationskomplexität untersucht man den Kommunikationsaufwand, der erforderlich ist, um ein Problem zu lösen, wenn die Eingabe für das Problem auf zwei oder mehr Parteien verteilt ist. Ein Überblick über das Gebiet soll erarbeitet werden.

Literatur:

• Anup Rao, Amir Yehudayoff, Communication complexity and applications, Cambridge, 2020.  
• Eyal Kushilevitz, Noam Nisan, Noam, Communication complexity. Cambridge, 2006.

Die Klasse TFNP besteht aus den totalen Funktionen, die in nichtdeterministischer Polynomialzeit berechnet werden können. Das heißt, es handelt sich um die Klasse der Funktionsprobleme, für die garantiert eine Antwort vorliegt, und diese Antwort kann in Polynomialzeit überprüft werden. Die Abkürzung TFNP steht für „Total Function Nondeterministic Polynomial“. Die wesentlichen komplexitätstheoretischen Resultate über diese Klasse sollen zusammengetragen werden.

Literatur:

• Nimro d Megiddo and Christos H Papadimitriou, A Note on Total Functions Existence Theorems and Computational Complexity, https://doi.org/10.1016/0304-3975(91)90200-L, 1989.
• John Fearnley et al., CLS: New Problems and Completeness, https://arxiv.org/pdf/1702.06017, 2017.

Ein Lifting-Theorem ist ein Satz, der eine untere Schranke in einem schwachen Berechnungsmodell in eine untere Schranke in einem starken Modell übersetzt. Ein Überblick über verschiedene derartige Resultate soll erarbeitet werden.

Literatur:

• Susanne F. de Rezende et al., KRW Composition Theorems via Lifting, https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=9317931, 2020.

Das Konzept der Problemkerne (engl. problem kernels) in der Komplexitätstheorie bezieht sich auf die Reduktion eines Problems auf eine kleinere, äquivalente Instanz, deren Größe nur von einem Parameter abhängt und nicht von der gesamten Eingabegröße. Diese Reduktion erfolgt durch Datenreduktionsregeln, die in polynomieller Zeit anwendbar sind und die ursprüngliche Instanz auf eine kleinere Instanz reduzieren, die denselben Parameterwert beibehält. Ein Problemkern ist somit der "schwierige" Teil einer Instanz eines NP-schweren Problems, der nach Anwendung der Reduktionsregeln übrig bleibt. Probleme, die in der Klasse FPT (Fixed-Parameter Tractable) liegen, besitzen Problemkerne, deren Größe durch eine Funktion des Parameters beschränkt ist. Die Methode der Problemkern-Reduktion ist besonders nützlich, um die Laufzeit von Algorithmen für schwierige Probleme zu verbessern, indem die Größe der zu bearbeitenden Instanz reduziert wird. In der Arbeit sollen die Grundlagen und Konzepte zu Problemkernen dargestellt werden.

Literatur:

• Rodney G. Downey, Michael R. Fellows: Fundamentals of Parameterized Complexity. Texts in Computer Science, Springer 2013, ISBN 978-1-4471-5558-4, pp. I-SSS, 3-707

In der Informatik lassen sich viele Probleme so modellieren, dass aus gewissen Basiselementen durch festgelegte Operationen (Abschlussoperationen) neue Elemente generiert werden. Für verschiedene Spezialfälle ist die genaue Komplexität der Aufzählung aller generierten Elemente bekannt. Die Resultate sollen wiedergegeben werden.

Literatur:

• Arnaud Mary ORCID und Yann Strozecki, Efficient enumeration of solutions produced by closure operations, dmtcs.episciences.org/5549, 2019

Matroide sind mathematische Strukturen, in denen Abhängigkeiten zwischen Elementen herrschen. Sie finden Anwendung in vielen Bereichen der Informatik, insbesondere der kombinatorischen Optimierung und Graphentheorie. Die Existenz von Greedy-Algorithmen für algorithmische Probleme kann oft auf eine zugrundeliegende Matroid-Struktur zurückgeführt werden.  
In diesem Bereich sind einige Abschlussarbeiten zu vergeben. Mögliche Themen sind:

1. Darstellung der Grundzüge der mathematischen Matroid-Theorie
2. Darstellung der Zusammenhänge zwischen Matroiden und Greedy-Algorithmen
3. Darstellung und Analyse beispielhafter Algorithmen, bspw. das Berechnen von Spannbäumen oder das Finden aller Kreise eines Graphen.

Literatur:

• D. J. A. Welsh: Matroid Theory (= L.M.S. Monographs. Band 8). Academic Press, London, New York, San Francisco 1976.  
• Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization. Algorithms and Complexity. Prentice Hall, Englewood Cliffs (NJ) 1982.  
• L. Khachiyan, On the Complexity of Some Enumeration Problems for Matroids, https://doi.org/10.1137/S0895480103428338, 2006.

Die Klasse ETR (oder auch ∃R) besteht aus allen Sprachen, die sich auf die Frage der Gültigkeit von Formeln über den reellen Zahlen mit Existenzquantor reduzieren lassen. Die Klasse ist zwischen NP und PSPACE angesiedelt. Sie enthält viele kontinuierliche geometrische Probleme, die sich als Verallgemeinerungen von NP-vollständigen Sprachen auf den reellen Grundbereich ergeben. Strukturelle Beziehungen und Vollständigkeitsresultate sollen zusammengefasst und dargestellt werden.

Literatur:

• Mikkel Abraham et al., The Art Gallery Problem is ∃R-complete, https://dl.acm.org/doi/10.1145/3486220, 2021.
• Saugata Basu et al., Existential Theory of the Reals. In: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, vol 10. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-33099-2_14

Bei dem Problem PosSLP geht es darum festzustellen, ob eine ganze Zahl, die durch ein gegebenes nicht-verzweigendes Programm (engl. straight line program) berechnet wird, positiv ist. Dieses Problem charakterisiert die Komplexität vieler mit numerischen Berechnungen definierten Problemen. Allerdings ist die genaue Komplexität von PosSLP unbekannt, lediglich verschiedene untere und obere Schranken sind bekannt, die in dieser Arbeit wiedergegeben werden sollen.

Literatur:

• Peter Bürgisser, Gorav Jindal, On the Hardness of PosSLP, https://arxiv.org/abs/2307.08008, 2023.
• Eric Allender et al., On the Complexity of Numerical Analysis, https://epubs.siam.org/doi/10.1137/070697926, 2009.

Hierarchien von Komplexitätsklassen, deren Ressourcenschranke nicht elementar ist, d.h. schneller wächst als jeder Turm von Exponentialfunktionen fester Höhe, werden in einer Arbeit von S. Schmitz untersucht. Eine neue Komplexitätsklasse TOWER spielt eine wichtige Rolle. Die Ergebnisse sollen zusammengefasst werden.

Literatur:

• Sylvain. Schmitz, Complexity Hierarchies beyond Elementary, https://doi.org/10.1145/2858784.

Das von Ryan Williams 2010 erzielte vielleicht bahnbrechendste Resultat der Komplexitätstheorie der letzten vier Jahrzehnte betrifft Schranken der Berechnungskraft von sog. ACC-Schaltkreisfamilien, Schaltkreisfamilien konstanter Tiefe, die neben den üblichen Gattern für Konjunktion, Disjunktion und Negation auch Gatter für Modulo-Tests verwenden dürfen. Das Resultat soll nachvollzogen werden. Der Beweis beruht auf einem sehr überraschenden Zusammenhang, in dem eine obere Schranke zu einer unteren Schranke führt: Williams zeigt, dass für viele Schaltkreisklassen schnellere Satisfiability-Algorithmen zu unteren Schranken führen.

Literatur:

• Ryan Williams, Improving exhaustive search implies superpolynomial lower bounds, https://doi.org/10.1137/10080703X, 2013.
• Ryan Williams, Nonuniform ACC Circuit Lower Bounds, https://doi.org/10.1145/2559903, 2014.

Beziehungen zwischen der Computational Social Choice Theory und der Komplexitätstheorie sollen zusammengefasst werden.

Literatur:

• Felix Brandt et al (Hrsg.), Handbook of Computational Social Choice, 2016. https://www.tib.eu/de/suchen/id/gwlb:883311291/Handbook-of-computational-social-choice?cHash=f09170ab9ad60030c92e3decdf6273dd

Von vielen wichtigen Komplexitätsklassen ist bekannt, dass sie aus sehr einfachen Funktionen (Nachfolger, Identität, etc.) mit Hilfe verschiedener Rekursionsschema generiert werden können. Einzelresultate dieses Gebietes sollen dargestellt werden.

Theoretische Untersuchungen der Berechnungskraft (optimal trainierter) neuronaler Netze, der Komplexität des Lernprozesses, der Beziehung zu diversen logischen Kalkülen wurden in den letzten Jahren veröffentlicht. Ergebnisse aus diesem sehr aktuellen Forschungsbereich sollen vorgestellt und zusammengefasst werden. Es sind verschiedene Bachelor- und Master-Arbeiten möglich!

Literatur:

• Gustav Šír, From Graph ML to Deep Relational Learning, https://towardsdatascience.com/from-graph-ml-to-deep-relational-learning-f07a0dddda89.
• Michael Benedikt et al, Decidability of Graph Neural Networks via Logical Characterizations, 2024. https://doi.org/10.4230/LIPIcs.ICALP.2024.127
• Lena Strobl et al, What Formal Languages Can Transformers Express? A Survey, 2024, https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00663/120983/What-Formal-Languages-Can-Transformers-Express-A
• Adrian Wurm, Complexity of Reachability Problems in Neural Networks, 2024. https://www.springerprofessional.de/complexity-of-reachability-problems-in-neural-networks/26128096

Die hinter Large Language Models wie ChatGPT stehende Netzwerk-Architektur der Transformer ist schwer handhabbar. Mit RASP wurde jedoch eine Programmiersprache entwickelt, deren Programme sozusagen in Transformer kompiliert werden können. Die Sprache, eine eingeschränkte (Bool’sche) Variante B-RASP sowie die Beziehungen zu Transformern sollen dargestellt werden.

Literatur:

• Gail Weiss, Yoav Goldberg, Eran Yahav, Thinking Like Transformers, https://proceedings.mlr.press/v139/weiss21a.html, 2021.
• Andy Yang, David Chiang, Dana Angluin, Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages, https://arxiv.org/abs/2310.13897, 2024.

In der Quantenmechanik werden nicht erklärbare oder zufällige Phänomene teilweise auf das Vorhandensein sog. verborgener Variablen oder Parameter zurückgeführt. Die sog. Teamlogik erlaubt eine rein logische Beschreibung und Analyse dieser Phänomene. Ein Überblick über das Gebiet soll gegeben werden.

Literatur:

• Rafael Albert und Erich Grädel, Unifying Hidden-Variable Problems from Quantum Mechanics by Logics of Dependence and Independence, www.sciencedirect.com/science/article/pii/S0168007222000021, 2022.

In der Linguistik wird seit einigen Jahren die mathematische Logik verwendet, um die Semantik natürlicher Sprachen zu beschreiben. Insbesondere findet hier die sog. Teamlogik Anwendung. Ergebnisse aus diesem neuen Forschungsbereich sollen vorgestellt und zusammengefasst werden.

Literatur:

• Maria Aloni, Logic and Conversation: The Case of Free Choice, https://semprag.org/index.php/sp/article/view/sp.15.5, 2022.
• Maria Aloni et al., State-based Modal Logics for Free Choice, https://www.researchgate.net/publication/370937884_State-based_Modal_Logics_for_Free_Choice, 2023.

Viele Beziehungen zwischen Komplexitätsklassen sind trotz jahrzehntelanger Forschungen noch ungeklärt; am bekanntesten ist das P-NP-Problem, also die Frage, ob die Klassen P und NP zusammenfallen. In der Logik wurde die Frage untersucht, ob das P-NP-Problem und weitere offene Fragen vielleicht gar nicht mit mathematisch-logischen Mitteln gelöst werden können. Aussagen, die in einer bestimmten logischen Theorie weder bewiesen noch widerlegt werden können, nennt man unabhängig von der Theorie. Erstaunlich einfache Unabhängigkeitsresultate sind bekannt. In dieser Arbeit soll ein Überblick über diese Untersuchungen gegeben werden.

Literatur:

• A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory https://arxiv.org/abs/1605.04343

Prädikatenlogische Theorien sind im Allgemeinen unentscheidbar. Für viele bedeutende eingeschränkte Theorien sind jedoch Entscheidungsalgorithmen bekannt. Einzelresultate aus diesem Gebiet sollen nachvollzogen werden. Rein theoretische Abschlussarbeiten, aber auch solche mit Implementationsaspekt sind möglich.

In diesem Bereich sind nur noch einzelne Fragestellungen als Thema für eine Abschlussarbeit verfügbar - sprechen Sie uns diesbezüglich bei Interesse einfach an.

Literatur:

• Egon Börger et al., The Classical Decision Problem, Springer-Verlag, 1997.