Logo Leibniz Universität Hannover
Logo:Institut für Theoretische Informatik
Logo Leibniz Universität Hannover
Logo:Institut für Theoretische Informatik
  • Zielgruppen
  • Suche
 

Themenübersicht Abschlussarbeiten

Wenn Sie an anderen Themen interessiert sind oder eigene Vorschläge haben, wenden Sie sich bitte an einen unserer Mitarbeiter. Prinzipiell kann jedes Thema im Umfang angepasst werden, sodass es für eine Bachelor-, Master- oder Diplomarbeit passend ist.

Algorithmen

Starke Hintertüren in Default Logik

Gegeben eine aussangelogische Formel sowie eine Teilmenge ihrer Variablen X. Man sagt X ist eine starke HORN-Hintertür für die Formel, wenn für alle Belegungen über der Variablen aus X die resultierende Formel eine HORN-Formel ist.

Default Logik ist ein Erweiterungen 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, dann 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 wieder. 

Kürzlich haben Fichte und weitere [1] das Konzept von Hintertüren in Default Logik eingeführt und im Gerüst der parametrisierten Komplexität analysiert.

In einer weiteren Veröffentlichung von Egly und weitere [2] wurde ein Framework entwickelt mit dem Probleme aus der Polynomialzeithierarchie über QBF-Formeln und dann QBF-Reasonern gelöst werden können.

In der Arbeit soll das Framework von [2] auf die Resultate in [1] angewendet werden.

[1] https://link.springer.com/chapter/10.1007%2F978-3-319-40970-2_4

[2] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.9925

Meier

Neues zur Komplexität des TSP-Problems

TSP ist bekanntermaßen NP-vollständig und nicht mit konstantem Faktor approximierbar. Svensson, Tarnawski und Végh haben kürzlich jedoch einen APX-Algorithmus für eine Variante, das sog. asymmetrische TSP, gefunden.  Dieser Durchbruch in der Theorie der effizienten Algorithmen soll dargestellt werden.

Link: Gödel’s Lost Letter https://rjlipton.wordpress.com/2017/09/11/a-tsp-breakthrough/

Vollmer

Komplexitätstheorie

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, welche 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, gesucht sind die Menge der Teilbäume, welche die Formel erfüllen.

Meier

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 von AND, OR, NOT und MOD2 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.

Link: eccc.weizmann.ac.il/report/2017/022/

Meier

Maschinengrößen

In einem Blog-Eintrag von Gasarch wird über sogenannte Bounding Functions referiert. Eine Funktion f nennt man eine Bounding Function für zwei Maschinentypen (D, E), wenn eine Sprache L durch eine D- und E-Maschine akzeptiert werden kann und L von der E-Maschine der Größe n akzeptiert wird, dann kann L von einer E-Maschine der Größe höchstens f(n) akzeptiert werden.

In der Arbeit sollen die Resultate bzgl. DEA, NEA, DKA, NKA und LBA erläutert und in Bezug zueinander gesetzt werden. Hierzu gibt es in dem Blog-Eintrag Verweise auf Original-Literatur.

Meier

Catalytic Space

Eine neue Art, Speicherbedarf zu messen, würde kürzlich unter der Bezeichnung “katalytischer Speicher” untersucht. Dabei handelt es sich um Speicher, der für Zwischenrechnungen benutzt werden darf, aber danach wieder den ursprünglichen Inhalt aufweisen muss. Es geht also um die Frage, ob Speicher, der bereits Daten enthält, die erhalten bleiben müssen, dennoch für Berechnungen genutzt werden kann. Interessante komplexitätstheoretische Resultate sind bekannt, die zusammengefasst werden sollen.

 

Link: Catalytic Space http://bulletin.eatcs.org/index.php/beatcs/article/view/400

Vollmer

Minimale Schaltkreise

Das Problem der minimalen Schaltkreisgröße MCSP ist eines der wenigen bekannten Probleme aus der Klasse NP, von denen weder bekannt ist, ob es NP-vollständig ist, noch, ob es in Polynomialzeit lösbar ist. Es gehört also zu den sog. ``intermediate problems’’. Die bekannten Komplexitätsresultate über MCSP sollen zusammengefasst werden.

 

Link: Complexity of Complexity http://link.springer.com/chapter/10.1007%2F978-3-319-50062-1_6

Vollmer

New circuit lower bound I

Kürzlich wurde in einer Arbeit von R. Williams die Komplexitätsklasse ACC von NEXPTIME getrennt. Der Beweis soll nachvollzogen werden.

Siehe auch: Gödels Lost Letter

Vollmer

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.

Vollmer

Computational Social Choice Theory

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

Vollmer

Kolmogorov-Komplexität und Informationsgehalt

In der Kolmogorov-Komplexität misst man die Schwierigkeit eines Algorithmus durch die Länge des kürzesten Programms, das ihn implementiert. In dieser Arbeit soll dieses Konzept mit der Shannon’schen Informationstheorie verglichen werden.

Literatur:
Kolmogorov Complexity and Information Content
https://arxiv.org/abs/1710.06846

Vollmer

Entscheidbare Arithmetik

Die Theorie der Arithmetik ist unentscheidbar, d.h. die Gültigkeit eines Satzes der Logik der ersten Stufe über den natürlichen Zahlen mit den Operationen Multiplikation und Addition kann i. A. nicht algorithmisch überprüft werden. Schränkt man sich auf die Operation der Addition ein (sog. Presburger Arithmetik PA) ist die Fragestellung entscheidbar. In dieser Arbeit sollen Ergebnisse über Fragmente von PA, z. B.  hinsichtlich der Quantorenkomplexität, zusammengefasst werden. Es ergeben sich Vollständigkeitsresultate für zentrale Komplexitätsklassen.

Literatur:Complexity of Presburger Arithmetic with Fixed Quantifier Dimension. Theory Comput. Syst.30(4)423-428 ().

Complexity of Short Presburger Arithmetic https://arxiv.org/abs/1704.00249

Short Presburger Arithmetic is Hard https://arxiv.org/abs/1708.08179

Vollmer

Incremental Computation

Sogenannte inkrementelle Probleme sind parametrisierte Probleme für die zwei zusätzliche Eingaben \Delta und S (neben der üblichen Instanz x und dem Parameter k) definiert werden. Hierbei ist \Delta eine Menge an Änderungen an x und der andere ein Zeuge für die Mitgliedschaft von (x,k) zur parametrisierten Sprache.

In der Abschlussarbeit soll ein Überblick über die betrachteten Probleme mit deren komplexitätstheoretischen Resultaten geliefert werden. Mögliche Literatur ist

Ramalingam, G., Reps, T.: A categorized bibliography on incremental computation. In: Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages POPL’93, pp. 502–510. ACM (1993)

Desikan, P., Pathak, N., Srivastava, J., Kumar, V.: Incremental page rank computation on evolving graphs. In: Special interest tracks and posters of the 14th international conference on World Wide Web, WWW’05, pp. 1094–1095. ACM (2005)

Held, M., Huber, S.: Topology-oriented incremental computation of voronoi diagrams of circular arcs and straight-line segments. Comput. Aided Des. 41(5), 327–338 (2009)

Jakub Ł., Sankowski, P.: Optimal decremental connectivity in planar graphs. Theory of Computing Systems 59(1), 1–17 (2016)

sowie https://link.springer.com/article/10.1007/s00224-016-9729-6?no-access=true

Meier

Das Matching Problem

Ein Matching ist eine Teilmenge der Kanten eines Graphen, sodass nie zwei Kanten gewählt wurden, die einen Endpunkt teilen. Ein Matching ist perfekt, wenn jeder Knoten im Graph zu einer Matchingkante gehört.

Das Matching Problem behandelt die Frage nach der Berechnung eines perfekten Matchings eines Graphen.

Es ist seit dem Algorithmus' von Edmonds bekannt, dass das Problem in Polynomialzeit gelöst werden kann.

In dieser Arbeit soll einerseits die Historie der Resultate aufgezeigt und diskutiert werden sowie ein Einblick in die neusten Resultate gegeben werden.

https://eccc.weizmann.ac.il/report/2017/059/

Meier

Kryptographie

Public-Key-Kryptographie und Komplexitätstheorie

Die komplexitätstheoretischen Grundlagen der Public-Key-Kryptographie sollen dargestellt werden.

Literatur:
The Complexity of Public Key Cryptography https://eccc.weizmann.ac.il/report/2017/065/

Vollmer

Zero-Knowledge-Beweise

Ausgehend von der Arbeit von Berman et al. [1], sollen Zero-Knowledge-Beweise, deren Theorie und Anwendung in der Kryptographie sowie Verbindungen zur Public-Key-Kryptographie erläutert werden.

[1] https://eccc.weizmann.ac.il/report/2017/172/

Meier

Post-Quantum-Kryptographie

In dieser Arbeit soll ein Überblick über mögliche Ansätze im Bereich der Post-Quantum-Kryptographie geliefert werden. 

https://pqcrypto.org

Meier

Berechenbarkeit

Zufallszahlen in der Berechenbarkeitstheorie

Als Zufallszahlen werden Zahlen bezeichnet, die nicht komprimierbar sind, d. h., kein Algorithmus kann mehr Stellen der Zahl wiedergeben, als seine eigene Länge beträgt. Ein Beispiel sind die Chaitinschen Konstanten, gelegentlich "Zahlen der Weisheit" genannt. Die Existenz von Zufallszahlen hat weitreichende Konsequenzen in der Theorie der Berechenbarkeit und der formalen Beweissysteme.

Vollmer, Lück

Primitiv-rekursive Funktionen

Die LOOP-berechenbaren Funktionen sind in der Theorie als sog. primitiv-rekursive Funktionen bekannt. Eine Reihe klassischer Ergebnisse zu Teilklassen dieser wichtigen Funktionsklasse soll dargestellt werden.

A Survey of Classes of Primitive Recursive Functions https://eccc.weizmann.ac.il/report/2017/001/

Vollmer

Logik

Prädikatenlogik der zweiten Stufe

In der Prädikatenlogik der zweiten Stufe sind neben den “gewöhnlichen” Quantoren auch Quantoren über Relationsvariablen erlaubt. Diese Arbeit soll einen Überblick über diese Logik geben.

 

Link: Second-order and Higher-order Logic http://plato.stanford.edu/entries/logic-higher-order/

Vollmer

Nichtmonotone Logiken

Schlussfolgerungen im Alltag sind oft von der Art, dass Folgerungen bei Bekanntwerden neuer Fakten zurückgezogen werden müssen. Dies widerspricht der Monotonie formaler Logiken, bei denen die Hinzunahme von zusätzlichen Axiomen bisherige Schlüsse nicht ungültig macht.

 

Mögliche Themen für Abschlussarbeiten aus diesem Bereich sind:

 

Eine spezielle Form der nicht-monotonen Logik ist die sog. autoepistemische Logik, über die ein Überblick verfasst werden soll.

Link: Non-monotonic Logic http://plato.stanford.edu/entries/logic-nonmonotonic/

 

Die Komplexität des Erfüllbarkeitsproblems für nicht-monotone Logiken soll untersucht werden.

 

Link: Complexity Results for Nonmonotonic Logics  logcom.oxfordjournals.org/content/2/3/397.full.pdf

Vollmer

Modallogische Systeme

Wie in der Vorlesung “Logik und Formale Systeme” gezeigt, lassen sich bestimmte Eigenschaften von Kripke-Strukturen, wie Symmetrie oder Transitivität, durch modallogische Axiome beschrieben werden. Diese sog. Korrespondenztheorie soll mittels eines Lehrbuchs der Modallogik aufgearbeitet werden.

 

Link: Modal Logic https://plato.stanford.edu/entries/logic-modal/, Abschnitt 8 und 9

Vollmer

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 <i>unabhängig</i> 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

Vollmer

Konstruktive Mengen

In der mathematischen Logik wurden konstruktive Mengen von Kurt Gödel eingeführt. Grob gesprochen lassen sie sich induktiv durch einfache Operationen definieren. In dieser Arbeit sollen mögliche Anwendungen konstruktiver Mengen in der Komplexitätstheorie untersucht werden.

Siehe auch: Gödel's Lost Letter

Vollmer

Endliche Modelleigenschaft in modaler Logik

Endliche Modelleigenschaften spielen in modalen Logiken eine entschiedene Rolle in Fragestellungen bezüglich Komplexität und Entscheidbarkeit. Endliche Modelleigenschaften können durch verschiedene Techniken bewiesen werden. In dieser Arbeit sollen die Filtrations-, sowie die Selektionstechnik untersucht und dargestellt werden.

Siehe auch Shethmann, Filtration via bisimulation, 2004.

Vollmer

Quantifizierte Boole’sche Formeln

Quantifizierte Boole‘sche Logik ist zwischen Aussagenlogik und Prädikatenlogik angesiedelt. Wesentliche Aussagen über Erfüllbarkeit, Deduktion und Ausdrucksstärke sollen zusammengefasst werden.

Literatur:
H. Kleine-Büning u. Th. Letmann, Propositional Logic: Deduction and Algorithms, Cambridge Tracts in Theoretical Computer Science, Band 48, 1999.

Vollmer

Formale Sprachen

Äquivalenz von DPDAs

Die Äquivalenz von deterministischen Kellerautomaten ist entscheidbar. Der Beweis soll nachvollzogen werden.

Vollmer

Maschinelle Analyse eines umfangreichen natürlichsprachlichen Textcorpus

Mit der Sammlung Tusculum liegt eine umfangreiche Textsammlung lateinischer Texte elektronisch vor. In diesem Themengebiet sollen Werke der Sammlung maschinell analysiert werden, z. B. hinsichtlich

  • Statistische Analyse des Wortschatzes
  • Erstellung von Konkordanzen
  • Formalsprachliche Analyse grammatikalischer Phänomene usw.

Lateinische Sprachkenntnisse bilden keine notwendige Voraussetzung, wohl aber Programmierkenntnisse und Beherrschen formalsprachlicher Konzepte und Resultate (z. B. aus GThI).

In diesem Themengebiet sind mehrere Bachelor- und Master-Arbeiten mit unterschiedlichen Gewichtungen von Theorie- und Implementationsaspekten zu vergeben.

Vollmer