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)

  1. #1 Uli
    3. Mai 2012

    Eine Frage: “Es ist aber jedenfalls schon seit Ende der 90er Jahre aus einer Arbeit von Hass-Lagarian-Pippenger bekannt, daß Unverknotetsein in NP ist.”

    Sollte das nicht P heißen? Sonst wäre es ja eben NICHT mit polynomiellem Aufwand zu beweisen…

  2. #2 Thilo
    3. Mai 2012

    Die Abkuerzung fuehrt leicht in die Irre: NP heisst nicht “not polynomial”, sondern “non-deterministic polynomial”.

    Auf deutsch:
    NP heisst nicht unbedingt, dass sich das Problem nicht in polynomieller Zeit loesen laesst. NP bedeutet, dass sich die Richtigkeit einer “geratenen” Loesung in polynomieller Zeit ueberpruefen laesst.
    P ist also eine Teilmenge von NP.

  3. #4 rolak
    8. Dezember 2012

    ts ts ts, da stolpere ich in der aktuellen TvF-CCIL über ‘Knoten’, denke endlich wieder an den Artikel, der mir vor anderthalb Wochen nähergebracht worden ist, suche den erinnerten thread für eine Frage, nur um festzustellen, daß hier schon ein entsprechender Nachsatz zu finden ist…

    –Heißt das, es hat sich nichts getan in den letzten zwei Monaten? (Nicht daß das erwartet gewesen wäre)
    –Mal abgesehen davon, daß mir das alles ungemein interessant vorkommt und sofort Knotenmuster vor dem inneren Auge generiert – gibt/gäbe es eine jetzt schon bekannte ‘praktische Auswirkung’, einen irgendwie spürbaren vorher→nachher Übergang?

  4. #5 Thilo
    8. Dezember 2012

    Dake fuer den Hinweis. Der Artikel in der ZEIT bezieht sich auf einen anderen Ansatz als den von Greg Kuperberg, den ich hier im Artikel besprochen hatte. In der ZEIT geht es um diese Arbeit von Chad Musick, die schon seit Oktober vorigen Jahres auf dem ArXiv liegt. Nachdem in der ersten Version ein Fehler gefunden worden war, hat Musick im April eine verbesserte Version aufs ArXiv gestellt. Anscheinend hat man in dieser neuen Version bisher keine Fehler gefunden, aber ich habe bisher auch noch keine “offizielle’ Bestaetigung gehoert, dass das Paper z.B. bei einer Zeitschrift angenommen worden waere. (Siehe auch http://ldtopology.wordpress.com/2012/10/18/untangling-a-knot/ ) Selbst gelesen habe ich die Arbeit auch noch nicht …

  5. #6 Thilo
    8. Dezember 2012

    Falls die Sache sich bestaetigt, werde ich hier natuerlich noch mal drueber schreiben. Musicks Beweis scheint konstruktiv zu sein, d.h. er liefert wirklich einen Algorithmus, der Knoten in polynomieller Zeit entknotet.

  6. #7 rolak
    8. Dezember 2012

    ok, also abwarten und (bei der aktuellen Wetterlage besonders heißen) Tee trinken…

  7. #8 Thilo
    4. April 2016

    Heute auf dem ArXiv: ein Beweis (ohne GRH) dass Verknotetsein in NP ist: http://arxiv.org/pdf/1604.00290.pdf