Die Komplexität des Graphisomorphieproblems im klassischen und quantentheoretischen Modell
Forschungsprojekt
Das Projekt wird von dem Deutschen Akademischen Austauschdienst (DAAD) und DST gefördert.
Zeitraum: 2003 bis 2006
Projektleiter: Prof. Johannes
Köbler, Prof. V.
Arvind
Forschungsinhalt
Das Graphisomorphieproblem (GI), d.h. die Aufgabe zwei gegebene Graphen auf Isomorphie zu testen, ist aus komplexitätstheoretischer Sicht eines der faszinierendsten algorithmischen Probleme. Dies erklärt sich hauptsächlich aus der komplexitätstheoretischen Sonderstellung des Problems. Gelang für die meisten Berechnungsprobleme in der Klasse NP ohne bekannte Algorithmen mit polynomieller Laufzeit der Nachweis der NP-Vollständigkeit, so ist hingegen das Graphisomorphieproblem eines der wenigen verbleibenden natürlichen Kandidaten für Probleme mit Komplexität zwischen P und NP-vollständig. In den letzten Jahrzehnten wurden leichter zugängliche Varianten des Problems intensiv studiert, und für viele eingeschränkte Graphklassen wurden effiziente Algorithmen gefunden. In jüngster Zeit wurden sogar einige dieser Einschränkungen als vollständig für Klassen unterhalb von P bewiesen. Mit diesem Projekt wollen wir diese Untersuchungen zu eingeschränkten Varianten von GI im weiteren Kontext von verwandten gruppentheoretischen Problemen weiter vorantreiben. Ein Schwerpunkt liegt dabei auf der noch ungeklärten Beziehung von GI zu Quantenkomplexitätsklassen, wobei wir insbesondere den Transfer klassischer Techniken in die Welt der Quantenrechner prüfen. Motiviert durch die aufsehenerregenden Resulate von Shor ist das Fernziel ein effizienter Quantenalgorithmus für GI.