Michael Krüger: CoNP-Vollständigkeit des inversen Hamiltonkreisproblems

Eine Sprache liegt in NP, wenn sie von einer nichtdeterministischen Polynomialzeitturingmaschine akzeptiert wird. Eine solche Maschine akzeptiert eine Instanz x, falls es einen akzeptierenden Berechnungspfad gibt. Die Frage, ob es zu einer Instanz einen akzeptierenden Berechnungspfad (Beweis) gibt, wird bei inversen Problemen umgekehrt. Gefragt ist nun, ob es für eine gegebene Menge von Pfaden eine Instanz gibt, die genau auf diesen Pfaden akzeptiert wird.
Das inverse Hamiltonkreisproblem besteht demnach darin, zu entscheiden, ob es zu einer gegebenen Menge von Hamiltonkreisen (also Permutationen einer Knotenmenge) einen Graphen mit genau diesen Hamiltonkreisen gibt. Dazu genügt es den minimalen Graphen zu untersuchen, der die gegebenen Hamiltonkreise enthält (Die Kantenmenge ist die Vereinigung aller an den Kreisen beteiligten Kanten). Die gegebene Hamiltonkreismenge liegt genau dann im inversen Problem, wenn der obige minimale Graph keine weiteren Hamiltonkreise enthält. Folglich liegt das inverse Hamiltonkreisproblem in coNP.
Der Beweis der coNP-Härte mittels Reduzierung vom coNP-harten inversen 3SAT-Problem ist das Ziel des Vortrags.