Untersuchung der Komplexität des Graphenisomorphieproblems

• Antragsteller: Professor Dr. Jacobo Torán
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2005 bis 2011
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5436983

Die algorithmische Komplexität des Graphenisomorphieproblems (G1) soll von einem neuen Standpunkt aus untersucht werden, der drei wichtige Fortschritte der letzten Jahre auf dem Gebiet der Komplexitätstheorie berücksichtigt, die interessante Bezüge zu Gl haben. Diese drei Fortschritte sind: - die Entwicklung von Algorithmen für Quantenrechner, - die Verbesserung von Derandomisierungstechniken und - die ersten bekannten unteren Schranken für GI in Bezug auf Komplexitätsklassen.Mit jedem dieser Gebiete ist je eine zentrale Frage verbunden, die in diesem Projekt untersucht werden soll, nämlich die Existenz von effizienten Quantenalgorithmen für Graphenisomorphie und ähnlich strukturierten Problemen, die Derandomisierung von interaktiven Protokollen für GI und die Verbesserung der existierenden unteren Schranken für GI. Weitere Aspekte dieser Untersuchungen betreffen neue (klassische) Algorithinen für eingeschränkte Graphklassen und konkrete explizite und implizite Graphdarstellungen.

• DFG-Verfahren: Sachbeihilfen