Studien- und Abschlussarbeiten

Das Konzept der Baumweite in der Graphentheorie beschreibt, wie "baum-ähnlich" ein Graph ist. Eine Baumzerlegung eines Graphen 𝐺 besteht aus einem Baum 𝑇 und einer Familie von Mengen (Bags), die bestimmte Bedingungen erfüllen, wie z.B. dass jede Kante von 𝐺 in mindestens einem Bag enthalten ist und die Bags, die einen Knoten enthalten, einen zusammenhängenden Teilbaum in 𝑇 bilden. Die Baumweite eines Graphen ist die minimale Weite aller möglichen Baumzerlegungen, wobei die Weite einer Baumzerlegung als die Größe der größten Tasche minus eins definiert ist. Graphen mit kleiner Baumweite sind algorithmisch interessant, da viele NP-schwere Probleme auf solchen Graphen effizient lösbar sind. Ein Graph hat Baumweite höchstens 1, wenn er ein Wald ist, und höchstens 2, wenn er keinen vollständigen Graphen 𝐾4 als Minor enthält. In der Arbeit sollen die Grundlagen zu Baumweite aufgearbeitet werden sowie die Probleme, die damit in Zusammenhang stehen definiert und algorithmisch betrachtet werden.

Literatur:

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

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.

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

Angenommen, ein Jeep kann maximal n Liter Benzin mitführen und fährt c Kilometer pro Liter. Der Jeep soll eine x Kilometer breite Wüste durchqueren. Beim Jeep Problem geht es darum, eine Methode zu finden, mit der die Reise am wirtschaftlichsten durchgeführt werden kann und am wenigsten Kraftstoff verbraucht wird.

Das n-Vehicle-Exploration-Problem (NVEP) wird als eine Variante des Jeep-Problems betrachtet, bei dem ein Konvoi von Jeeps zusammen fährt, von denen einige zum Auftanken der anderen genutzt werden, wobei nur ein Jeep die maximale Entfernung zurücklegen muss. In dieser Arbeit soll mit der folgenden Literatur gearbeitet weden und unter anderem ein NP-Vollständigkeitsbeweis für NVEP dargestellt werden.

Literatur:

• Fine, N.J.: The jeep problem. Amer Mach Monthly 54, 24–31 (1947) https://www.jstor.org/stable/2304923?seq=1 - Jinchuan Cui, Xiaoya Li: The n-vehicle exploration problem is NP-complete. CoRR abs/2304.03965 (2023)
• Jinchuan Cui, Xiaoya Li: The n-vehicle exploration problem is NP-complete. CoRR abs/2304.03965 (2023)

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:

• Darstellung der Grundzüge der mathematischen Matroid-Theorie
• Darstellung der Zusammenhänge zwischen Matroiden und Greedy-Algorithmen
• 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.

In dieser Arbeit soll ein aktuelles Resultat nachvollzogen und im Gesamtkontext dargestellt werden. Es geht um den Vergleich der Mächtigkeit von Formeln und Schaltkreisen. AC0[xor]-Schaltkreise verwenden Gatter der Form AND, OR, NOT und MOD 2 von unbeschränktem Eingangsgrad. Bei der Fragestellung handelt es sich um eine Einschränkung der generellen Frage, ob NC1 (Sprachen, für die es polynomiell große Boole'sche Formeln gibt) eine echte Teilklasse von P/poly (Sprachen, für die es einen polynomiell großen Boole'schen Schaltkreis gibt) ist.

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

Literatur:

• https://arxiv.org/pdf/1710.10753.pdf
• https://arxiv.org/pdf/1711.00201.pdf

In den vergangenen etwa 10 Jahren wurden zahlreiche Beziehungen zwischen Laufzeiten optimaler Algorithmen für kombinatorische Probleme gefunden, z. B. zwischen der Laufzeit des All-pairs-Shortest-Path-Problem und der des Triangle-Problems. Zu dem Themengebiet liegen verschiedene Überblickartikel und Skripten vor (siehe etwa [1]). Ein Überblick über das Gebiet soll verfasst werden.

Literatur:

• https://eta.impa.br/dl/194.pdf

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.

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.

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, https://www.sciencedirect.com/science/article/pii/S0168007222000021, 2022.

Klassen neuronaler Netze, die eine innere Struktur aufweisen, werden derzeit stark untersucht. Die bestehende Literatur soll gesichtet und zusammengefasst werden. 

Literatur:

• Gustav Šír, From Graph ML to Deep Relational Learning, https://towardsdatascience.com/from-graph-ml-to-deep-relational-learning-f07a0dddda89

Die Berechnungskraft gewisser Klassen neuronaler Netze (sog. Graph Neural Networks) wurde kürzlich mit Hilfe der Modallogik und der Prädikatenlogik mit zwei Variablen charakterisiert. Die Resultate sollen nachvollzogen und möglichst erweitert werden.

Literatur:

• Pablo Barceló, Egor V. Kostylev, Mikaël Monet, Jorge Pérez, Juan L. Reutter, Juan Pablo Silva, The Logical Expressiveness of Graph Neural Networks, https://openreview.net/forum?id=r1lZ7AEKvB.

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.