Ist das 3-Sphären-Erkennungsproblem NP-vollständig?

13

Es ist bekannt, dass die Bestimmung, ob eine gegebene triangulierte 3-Mannigfaltigkeit eine 3-Sphäre ist oder nicht, in NP erfolgt, über eine Arbeit von Saul Schleimer im Jahr 2004: "Die Sphärenerkennung liegt in NP" arXiv: math / 0407047v1 [math.GT] . Ich frage mich, ob sich herausgestellt hat, dass dies in den letzten fünf oder sechs Jahren NP-vollständig war. Analoge Probleme, wie das 3-Mannigfaltigkeitsknoten-Gattungsproblem, sind NP-vollständig gezeigt worden.

Joseph O'Rourke
quelle
3
Das Problem ist nun bekanntermaßen auch im Co-NP zu finden, siehe die Ankündigung in J. Hass, Neue Ergebnisse zur Komplexität der Erkennung der 3-Sphären, Oberwolfach Rep. 9 (2012), Nr. 2, 1425 {1426.
Arnaud
@ Arnaud: Gibt es ein Update dazu? Ich konnte seitdem nichts von Hass über das Problem finden. Das beste, was ich finden konnte, ist das von GRH abhängige coNP-Ergebnis, das ich in meine neue Antwort eingegeben habe, und das scheint Hass nicht zu erwähnen :(.
Joshua Grochow,
@JoshuaGrochow Entschuldigung, mein Kommentar war ungenau und diese Behauptung von Joel Hass (ich habe auch vergessen zu sagen, dass dies bei G. Kuperberg war) ging ebenfalls von GRH aus. Soweit ich weiß, ist eine vollständige Beschreibung noch nicht erschienen.
Arnaud

Antworten:

15

Wenn es NP-vollständig ist, hätten Sie dann nicht bewiesen, dass kein Satz von (einheitlich) durch Polynomzeit berechenbaren Invarianten von 3-Mannigfaltigkeiten 3-Kugeln von anderen 3-Mannigfaltigkeiten unterscheidet. Ich wäre sehr überrascht, wenn dies bekannt ist.

Peter Shor
quelle
3
Insbesondere würde ein NP-Härte-Ergebnis beweisen, dass die 3-Sphären in der Polynomzeit nicht von anderen Homologie-3-Sphären unterschieden werden können.
Jeffs
7

Um Peters Antwort zu ergänzen: Hass, Lagarias und Pippenger haben gezeigt, dass das Problem der Knotenfreiheit in der Drei-Sphären-Sphäre im NP liegt. Ian Agol hat bewiesen, dass das Problem des Entknotens im Co-NP liegt (siehe jedoch seine Kommentare zu MathOverflow). Zumindest für mich ist das Problem der Drei-Sphären-Erkennung weitaus ähnlicher mit dem Entknoten als mit dem Verknoten von Gattungen im Allgemeinen mit drei Mannigfaltigkeiten. (Weil es durch das Vorhandensein einer positiven Euler-charakteristischen Oberfläche zertifiziert ist.)

Daher würde ich wetten, dass die Drei-Sphären-Erkennung auch im Co-NP enthalten ist. Ein Schritt in diese Richtung wäre zu zeigen, dass die Erkennung irreduzibler toroidaler Mannigfaltigkeiten in NP erfolgt, direkt nach Agol. Etwas stärker wäre zu zeigen, dass Haken vielfältige Anerkennung in NP liegt. Schwieriger ist es, die Dreikugel von den irreduziblen, nicht torusförmigen Verteilern zu trennen. Aber vielleicht ist die Geometrisierung das Richtige für Sie - wenn der Verteiler geschlossen, orientierbar, irreduzierbar und atoroidal ist, hat er eine der acht Thurston-Geometrien. Vielleicht ist es einfach, alle geometrischen, aber nicht hyperbolischen Mannigfaltigkeiten zu zertifizieren, beispielsweise über fast normale Heegaard-Teilungen. (Obwohl die Komplexitätsgrenzen von Hass, Lagarias und Pippenger irgendwie ersetzt werden müssten.)

Bescheinigung, dass ein dreifacher M eine hyperbolische Struktur hat, klingt schwieriger. Zwei Ideen liegen auf der Hand:

MNNNM

M

Sam Nead
quelle
3

Dieses Papier zeigt (obwohl ich es nicht verifiziert habe), dass die 3-Sphären-Erkennung * in coNP unter der Annahme von GRH erfolgt:

SL(2,C)

(Möglicherweise von Interesse: ein Folgepapier arXiv: 1610.04092 [math.GT] verwendet dieses, um einen Algorithmus auf der Basis von Grobner zu entwickeln.)

* Technisch wird angegeben, dass das Erkennen der 3-Sphäre unter der Ganzzahlhomologie 3-Sphären in coNP unter der Annahme von GRH erfolgt. Ich bin kein Experte auf diesem Gebiet, aber es scheint mir klar, dass man die ganzzahlige Homologie bei gegebener Triangulation in Polyzeit berechnen kann, und wenn die ganzzahlige Homologie nicht mit der einer 3-Sphäre übereinstimmt, ist dies definitiv nicht der Fall die 3-Sphäre.

Joshua Grochow
quelle