Prof. Dr. Johannes Köbler

Prof. Köbler erforscht grundlegende Fragen der Komplexitätstheorie, insbesondere das Graphenisomorphie-Problem und die Kanonisierung von Graphen — zentrale Herausforderungen der Theoretischen Informatik. Sein Fokus liegt darauf, die rechnerische Schwierigkeit dieser Probleme zu verstehen und effiziente Algorithmen zu entwickeln. Die Ergebnisse sind relevant für Anwendungen, die Strukturvergleiche oder Normalisierung von Netzwerkdaten erfordern, etwa in der Chemoinformatik, Bioinformatik oder bei der Verifikation von Schaltkreisen und Softwaresystemen.

🔒 Das System hat 393 mögliche Industrie-Partner gefunden — Firmen, Scores und Begründungen sind nur für eingeloggte Nutzer:innen sichtbar. Anmelden

• Aussagenlogische 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>

• Optimal proof systems imply complete sets for promise classes

  2003

  Information and Computation · DOI

• Completeness results for graph isomorphism

  2003

  Journal of Computer and System Sciences · DOI

• On Weisfeiler-Leman invariance: Subgraph counts and related graph properties

  2020

  Journal of Computer and System Sciences · DOI