Unentknotbarkeit läßt sich (wahrscheinlich) in polynomieller Zeit überprüfen.
Am Sonntag hatten wir über den neuen Film “Travelling Salesman” geschrieben – der uns die weltbewegenden Konsequenzen von P=NP aufzeigen soll, zum Beispiel einen in polynomieller Zeit arbeitenden Algorithmus zur Lösung des Problems des Handelsreisenden.
Bei P=NP geht es um zwei Klassen von Problemen: P sind diejenigen Probleme, die sich durch einen in polynomieller Zeit arbeitenden Algorithmus lösen lassen und NP sind diejenigen Probleme, für die sich zumindest die Richtigkeit einer gegebenen Lösung in polynomieller Zeit überprüfen läßt. Viele wichtige Probleme (u.a. das des Handelsreisenden) sind in der Klasse NP und wenn P=NP wäre, dann ließen sich alle diese Probleme in polynomieller Zeit lösen.
Gibt es polynomielle Algorithmen, mit denen man die Entknotbarkeit eines Knotens entscheiden kann? Oder gibt es zumindest einen polynomiellen Algorithmus, mit dem man die Entknotbarkeit eines unverknoteten Knotens überprüfen kann?
Mit anderen Worten: ist das Problem der Entknotbarkeit in P oder zumindest in NP?
Zahlreiche YouTube-Videos zeigen, daß das Entknoten eines unverknoteten Knotens keineswegs trivial ist:
Der historisch erste Algorithmus, mit dem Entknotbarkeit eines Knotens entschieden werden kann, stammt von Wolfgang Haken und benutzt die Theorie der Normalflächen. Dieser Algorithmus ist aber nicht effektiv, insbesondere nicht polynomiell, und läßt sich in der “Praxis” nicht wirklich anwenden. Es ist aber jedenfalls schon seit Ende der 90er Jahre aus einer Arbeit von Hass-Lagarian-Pippenger bekannt, daß Unverknotetsein in NP ist. Heißt: wenn man einen unverknoteten Knoten hat, dann läßt sich in polynomieller Zeit beweisen, daß er unverknotet ist.
Offen war aber bisher die Frage ob Unentknotbarkeit, also Verknotetsein, in NP ist. (Es gibt einen Vortrag von Ian Agol über einen Ansatz mittels Normalflächentheorie, der zeigen würde, daß die Berechnung des Geschlechts von Seifertflächen in NP ist. Das wäre allgemeiner als die Frage nach Unentknotbarkeit, denn ein Knoten ist unverknotet gdw. seine Seifertfläche Geschlecht 0 hat.)
Wie jetzt gezeigt wurde, ist die Antwort wahrscheinlich positiv. Jedenfalls hat Greg Kuperberg vor knapp 5 Monaten einen Preprint “Knottedness is in NP, modulo GRH” auf das ArXiv gestellt. Dort beweist er:
Theorem 1.1. Let K ⊆ S3 be a knot described by a knot diagram, a generalized triangulation, or an incomplete Heegaard diagram.
Then the assertion that K is knotted is in NP, assuming the generalized Riemann hypothesis (GRH).
GRH ist die Verallgemeinerte Riemann-Vermutung, welche besagt, daß die Nullstellen s der L-Funktion eines Dirichlet-Charakters (mit Realteil Re(s) zwischen 0 und 1) alle auf der Geraden Re(s)=1/2 liegen müssen. Die GRH wird in Kuperbergs Beweis benötigt um zu beweisen, daß die Länge des Algorithmus tatsächlich polynomiell ist.
Kuperbergs Algorithmus baut auf der Arbeit “Dehn surgery, the fundamental group and SU(2)” von Kronheimer-Mrowka auf. Dort wurde gezeigt, daß die Fundamentalgruppe eines nichttrivialen Knotenkomplements eine nichtabelsche Darstellung in SU(2) hat. Aus GRH folgt, daß es eine solche Darstellung dann auch in SL(2,Z/pZ) für eine geeignete Primzahl p polynomieller Länge gibt. Die “Lösung”, mit der man das Verknotetsein beweisen kann, besteht hier also aus einer Primzahl p und Matrizen in SL(2,Z/pZ). (Letztere sollen die Bilder der Erzeuger der Fundamentalgruppe unter der Darstellung in SL(2,Z/pZ) sein.) Um zu beweisen, daß der Knoten verknotet ist, muß man überprüfen, daß diese Matrizen nicht alle kommutieren und natürlich, daß sie die in der Fundamentalgruppe geltenden Relationen erfüllen. Beides läßt sich in polynomieller Zeit überprüfen.
Greg Kuperberg (2011). Knottedness is in NP, modulo GRH ArXiv arXiv: 1112.0845v1
Kommentare (8)