THEMEN
Wenn Sie eigene Vorschläge haben, wenden Sie sich gerne an einen unserer Mitarbeiter. Prinzipiell kann jedes Thema im Umfang angepasst werden, sodass es für eine Bachelor-, Master- oder Diplomarbeit passend ist.
Algorithmen
-
Ein SAT-Algorithmus, der besser ist als man denkt.
Der Algorithmus von Paturi, Pudlak, Sacks und Zane war für eine lange Zeit der schnellste, bekannte Algorithmus für k-SAT. Aktuelle Untersuchungen zeigen, dass der Algorithmus exponentiell besser ist als bisher bekannt. In dieser Arbeit sollen die neusten Entwicklungen und Erkenntnisse nachvollzogen und zusammengefasst präsentiert werden.
Leitung und Ansprechpartner der Abschlussarbeit
-
Reachability in Neuronalen Netzwerken
In dieser Arbeit geht es um ein aktuell betrachtetes Erreichbarkeitsproblem im Kontext von neuronalen Netzen, bei dem, ausgehend von einer gültigen Eingabe, eine gültige Ausgabe berechnet wird. Kürzlich wurde dieses Problem in einer sehr eingeschränkten Form bereits als NP-vollständig klassifiziert. Es soll der Beweis nachvollzogen und mit Beispielen illustriert werden.
Quelle: http://arxiv.org/abs/2108.13179
Leitung und Ansprechpartner der Abschlussarbeit
-
Starke Hintertüren in Default-Logik
Gegeben eine aussangelogische Formel und eine Teilmenge X ihrer Variablen, sagt man, dass X eine starke HORN-Hintertür für die Formel ist, wenn für alle Belegungen über den Variablen aus X die resultierende Formel eine HORN-Formel ist.
Default-Logik ist eine Erweiterung einer Logik um sogenannte Default-Regeln. Diese Regeln sind Formel-Tripel bestehend aus einer Vorbedingung, einer Rechtfertigung und einer Schlussfolgerung. Gegeben eine Wissensbasis (Menge von Formeln) sowie eine Menge von Default-Regeln, fragt man in einem wichtigen Entscheidungsproblem nach der Existenz einer stabilen Erweiterung. Diese Erweiterungen spiegeln im Prinzip das folgerbare Wissen aus der Wissensbasis unter Anwendung der Default-Regeln wider.
Kürzlich haben Fichte und andere [1] das Konzept von Hintertüren in Default-Logik eingeführt und hinsichtlich seiner parametrisierten Komplexität analysiert.
In einer weiteren Veröffentlichung von Egly und anderen [2] wurde ein Framework entwickelt, mit dem Probleme aus der Polynomialzeithierarchie über QBF-Formeln gelöst werden können.
In der Arbeit soll das Framework von [2] auf die Resultate in [1] angewendet werden.
[1] Strong Backdoors for Default Logic. Johannes K. Fichte, Arne Meier, Irina Schindler (2016)
Leitung und Ansprechpartner der Abschlussarbeit
Komplexitätstheorie
-
Polygon-Triangulierung
Ein bekanntes Problem aus dem Bereich der 'Computational Geometry' ist
die sogenannte Polygon-Triangulierung. Hierbei geht es darum, ein
gegebenes Polygon in Dreiecke zu unterteilen. Die Anzahl aller
Polygon-Triangulierungen eines (nicht einfachen) Polygons zu berechnen,
ist #P-vollständig. (https://arxiv.org/pdf/1903.04737.pdf)
Im Rahmen der Abschlussarbeit sollen nun verschiedene Algorithmen
komplexitätstheoretisch analysiert werden und ggf. auf Spezialfälle
eingegrenzt werden oder Schwere- und Härteresultate von verwandten
Probleme bewiesen werden.Leitung der Abschlussarbeit
Ansprechpartner der Abschlussarbeit
-
Enumeration in modaler Logik
Enumerationskomplexität befasst sich mit der Ausgabe aller Lösung ohne Duplikate einer Eingabe. Hierbei handelt es sich häufig um Algorithmen mit exponentieller Laufzeit. Aus diesem Grund klassifiziert man diese deterministischen Algorithmen an Hand ihres Delays. Der Delay eines Algorithmus beschreibt die Zeit, die zwischen der Ausgabe von zwei Lösungen verstreicht. Hierbei gibt es zum Beispiel die Klassen DelayP und IncP. Problem in der Klasse DelayP besitzen solche Enumerationsalgorithmen, welche einen polynomiellen Delay in der Eingabelänge besitzen, bei IncP ist der Delay der i-ten Lösung ein Polynom in der Eingabelänge und des Lösungsindex.
In der Arbeit soll die Enumerationskomplexität von Problemen in der Modallogik betrachtet werden. Gegeben eine modallogische Formel sowie ein Model, ist die Menge der Teilbäume gesucht, die die Formel erfüllen.
Leitung und Ansprechpartner der Abschlussarbeit
-
Separation von Formeln und nicht-uniformen Schaltkreisen für AC0[xor]
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.
Leitung und Ansprechpartner der Abschlussarbeit
-
New circuit lower bound II
Die Permanente ist eine Eigenschaft von Matrizen und ist ganz ähnlich zur Determinante definiert, weist aber interessanterweise sehr unterschiedliche Komplexitätseigenschaften auf. Die bestehenden Resultate über die Komplexität der Permanente sollen zusammengefasst werden.
Siehe auch: Gödels Lost Letter
Leitung und Ansprechpartner der Abschlussarbeit
-
Computational Social Choice Theory
Beziehungen zwischen der Computational Social Choice Theory und der Komplexitätstheorie sollen zusammengefasst werden.
Leitung und Ansprechpartner der Abschlussarbeit
-
Fine-grained complexity
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.
Leitung und Ansprechpartner der Abschlussarbeit
-
Algebraische Charakterisierungen von Komplexitätsklassen
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.
Leitung und Ansprechpartner der Abschlussarbeit
Kryptographie
-
Einwegfunktionen aus NP-vollständigen Problemen
Eine Einwegfunktion ist eine Funktion, deren Bild schnell berechnet werden kann. Schnell bedeutet in diesem Kontext in Polynomialzeit. Zusätzlich soll die Funktion schwer umkehrbar sein. Hier gibt es mehrere Möglichkeiten dies mathematisch umzusetzen. Eine Möglichkeit ist die Forderung, dass die Wahrscheinlichkeit, dass ein beliebiger probabilistischer Polynomialzeitalgorithmus dies schafft, vernachlässigbar klein ist. In dieser Arbeit beschäftigt man sich mit einer kürzlichen Veröffentlichung zum Thema von Einwegfunktionen und NP-vollständigen Problemen. Die Resultate sollen zusammengefasst und präsentiert werden.
Leitung und Ansprechpartner der Abschlussarbeit
Logik
-
Abstract Argumentation
In diesem Framework, werden Argumente und deren Beziehungen zueinander graphisch modelliert. Die Argumente sind Knoten wohingegen die Kantenrelation darstellt, welche Argumente sich gegenseitig angreifen. Nun wird nach Knotenteilmengen gesucht, welche bestimmte Eigenschaften haben (z.B. dass die Menge sich gegen die Argumente von außerhalb verteidigt). In dieser Literaturarbeit soll ein Überblick über das Gebiet gegeben werden.
Quelle: https://content.iospress.com/articles/argument-and-computation/aac190476
Leitung und Ansprechpartner der Abschlussarbeit
-
Bipolare Argumentation Frameworks
Abstract Argumentation ist ein Framework, in dem Argumente und deren Beziehungen zueinander graphisch modelliert. Die Argumente sind Knoten wohingegen die Kantenrelation darstellt, welche Argumente sich gegenseitig angreifen. Nun wird nach Knotenteilmengen gesucht, welche bestimmte Eigenschaften haben (z.B. dass die Menge sich gegen die Argumente von außerhalb verteidigt). In dieser Arbeit beschäftigt man sich mit einer neuen Erweiterung dieses Frameworks und die Resultate sollen nachvollzogen und präsentiert werden.
Quelle: https://arxiv.org/abs/1903.01964
Leitung und Ansprechpartner der Abschlussarbeit
-
Claim-Augmented Argumentation Framewoks
Abstract Argumentation ist ein Framework, in dem Argumente und deren Beziehungen zueinander graphisch modelliert. Die Argumente sind Knoten wohingegen die Kantenrelation darstellt, welche Argumente sich gegenseitig angreifen. Nun wird nach Knotenteilmengen gesucht, welche bestimmte Eigenschaften haben (z.B. dass die Menge sich gegen die Argumente von außerhalb verteidigt). In dieser Arbeit beschäftigt man sich mit einer neuen Erweiterung dieses Frameworks und die Resultate sollen nachvollzogen und präsentiert werden.
Quelle: https://ojs.aaai.org/index.php/AAAI/article/view/16782
Leitung und Ansprechpartner der Abschlussarbeit
-
Logik-basierte Argumentation
Logikbasierte Argumentation ist ein etablierter Formalismus zur Modellierung nichtmonotoner Argumentation. Sie spielt in der KI schon seit Jahrzehnten eine wichtige Rolle. Informell ist eine Menge von Formeln die Unterstützung (Support) für eine gegebene Behauptung (Claim), wenn sie konsistent und minimal unter Teilmengenbildung ist und die Behauptung impliziert. In einem solchen Fall wird das Paar aus Unterstützung und Behauptung zusammen als Argument bezeichnet. In dieser Literaturarbeit soll ein Überblick über das Gebiet gegeben werden.
Quelle: https://www.aaai.org/Library/AAAI/2000/aaai00-063.php
Leitung und Ansprechpartner der Abschlussarbeit
-
Unabhängigkeitsresultate
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.
Link: A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory https://arxiv.org/abs/1605.04343
Leitung und Ansprechpartner der Abschlussarbeit
-
Komplexität logischer Theorien
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.
Siehe: Egon Börger et al., The Classical Decision Problem, Springer-Verlag, 1997.
Leitung und Ansprechpartner der Abschlussarbeit
