Prof. Dr. Johannes Köbler
Themen
Zusammenfassung
Prof. Dr. Johannes Köbler forscht auf dem Gebiet der Theoretischen Informatik mit einem Schwerpunkt auf dem Graphisomorphieproblem, der Komplexitätstheorie und der Beweiskomplexität. Seine Arbeit umfasst die Entwicklung und Analyse von Algorithmen, insbesondere des Weisfeiler-Leman-Verfahrens, sowie die Untersuchung algebraischer und kombinatorischer Methoden zur Lösung von Problemen in der Graphentheorie. Er befasst sich zudem mit aussagenlogischen Beweissystemen und deren Beziehungen zu disjunkten NP-Paaren, wobei er untere Schranken für Beweislängen nachweist. Seine Publikationen zeigen eine tiegreiche Auseinandersetzung mit der parametrisierten Komplexität und der Ausdrucksstärke verschiedener graphischer Invarianten.
Matches
909Details nur für eingeloggte sichtbar🔒 Das System hat 909 mögliche Industrie-Partner gefunden — Firmen, Scores und Begründungen sind nur für eingeloggte Nutzer:innen sichtbar. Anmelden
Stammdaten
Identität, Organisation und Kontakt aus HU-FIS.Prof. Dr. Johannes Köbler
- Institut
- Algorithmen und Komplexität II
Forschungsprojekte
6Aussagenlogische Beweiskomplexität und disjunkte NP-Paare I
Quelle ↗Im Projekt werden starke aussagenlogische Beweissysteme wie Erweiterungen von Frege-Systemen und ihre Beziehungen zu disjunkten NP-Paaren untersucht. Ein zentrales Problem ist der Nachweis unterer Schranken für die Beweislänge für starke Beweissysteme (unter geeigneten komplexitätstheoretischen Voraussetzungen). Ein wichtiges Hilfsmittel bilden hierbei die mit dem Beweissystem assoziierten kanonischen NP-Paare.
Aussagenlogische Beweiskomplexität und disjunkte NP-Paare II
Quelle ↗<p>Zur Analyse aussagenlogischer Beweissysteme wurden in den letzten Jahren neben logischen zunehmend kombinatorische, kryptografische und komplexitätstheoretische Techniken herangezogen, die neue Sichtweisen auf beweistheoretische Fragen eröffnen.</p> <p>Unter Ausnutzung dieser Techniken wollen wir im Projekt die Entwicklung einer allgemeinen Theorie zu Beweissystemen weiter vorantreiben. Dabei konzentrieren wir uns auf starke Beweissysteme wie Frege-Systeme, zu denen im Vergleich zu schwachen Systemen wie Resolution viele Fragen noch ungeklärt sind. Als ausdrucksstarkes Werkzeug haben sich hierbei im bisherigen Projektverlauf disjunkte NP-Paare erwiesen.</p> <p>Ein Schwerpunkt dieses Projektes liegt auf der Untersuchung charakteristischer Eigenschaften praktisch wichtiger Beweissysteme. Diese Eigenschaften wollen wir mit Hilfe disjunkter NP-Paare modellieren und im Verband der NP-Paare komplexitätstheoretisch analysieren. Ein weiteres Ziel ist der Einsatz kryptografischer Konzepte wie Pseudozufallsgeneratoren zum Nachweis unterer Schranken für die Beweislänge.</p> <p>Das Fernziel sind hier untere Schranken für erweiterte Frege Systeme. Auch zur Analyse solcher kryptografischen Annahmen wollen wir disjunkte NP-Paare einsetzen.</p>