Gibt es knotentheoretische Formulierungen für NP-Gesamtprobleme?

12

Gibt es vollständige NP-Probleme (oder sogar NP-harte oder NP-Probleme), die gute topologische Eigenschaften aufweisen, die untersucht werden müssen? Haben NP-Probleme knotentheoretische Formulierungen? Wir wissen über # Ergebnisse über das Jones-Polynom Bescheid . Graphprobleme (Einbettungen?), Insbesondere Färbungen von Graphen, haben gute knotentheoretische Eigenschaften. Es ist eine offene Frage, und alle Referenzen zu diesem Thema sind willkommen.P

user3483902
quelle

Antworten:

11

Sie können einen Blick werfen auf:

Peter Golbus, Robert W. McGrail, Tomasz Przytycki, Mary Sharac und Aleksandar Chakarov. 2009. Dreifarbige Torusknoten sind NP-vollständig . In Proceedings der 47. jährlichen Südost-Regionalkonferenz (ACM-SE 47). ACM, New York, NY, USA, Artikel 42, 6 Seiten.

Abstract: In dieser Arbeit wird eine Methode vorgestellt, mit der eine Klasse von Bedingungserfüllungsproblemen einem dreidimensionalen Knoten zugeordnet werden kann. Wenn ein Knoten gegeben ist, kann man einen Knotenquandle aufbauen, bei dem es sich im Allgemeinen um eine unendliche freie Algebra handelt. Die gewünschte Sammlung von Problemen wird aus der Menge der invarianten Beziehungen über dem Knotenquandle abgeleitet, wobei eine Theorie angewendet wird, die endliche Algebren mit Bedingungszufriedenheitsproblemen in Beziehung setzt. Dies ermöglicht es uns, Konzepte von traktierbaren und NP-vollständigen Quandles und Knoten zu entwickeln. Insbesondere zeigen wir, dass alle dreifarbigen Torusknoten und alle bis auf höchstens 2 nicht-triviale Knoten mit 10 oder weniger Kreuzungen NP-vollständig sind.

und auch zu seinem wegweisenden Bericht:

P. Golbus, RW McGrail, M. Merling, K. Ober, M. Sharac und J. Wood. Die Klasse der Bedingungszufriedenheitsprobleme über einen Knoten . Technischer Bericht Nr. BARD-CMSC-2008-01, Bard College, 2008.

Marzio De Biasi
quelle
9

Es gibt einige Verweise im ersten Absatz von

  • Marc Lackenby. Eine Polynomobergrenze für Reidemeister bewegt sich. arXiv: 1302,0180

Insbesondere sagt der Autor, dass das Problem der Erkennung, dass ein Knotendiagramm den Unknot darstellt, in , indem ein Ergebnis von Hass-Lagarias-Pippenger kombiniert wird (Unknotness ist in NP). mit unabhängigen Ergebnissen von Agol und Kuperberg (diese Verknotung ist in NP, wobei letzteres dies unter der Annahme der verallgemeinerten Riemann-Hypothese beweist). Das Agol-Ergebnis scheint unveröffentlicht zu sein, aber die anderen Referenzen sind:NPcÖNP

  • Joel Hass, Jeffrey C. Lagarias und Nicholas Pippenger. Die rechnerische Komplexität von Knoten- und Verbindungsproblemen. J. ACM 46 (1999) 185-211. arXiv: math / 9807016

  • Greg Kuperberg. Verknotung ist in NP, Modulo GRH. Dezember 2011, überarbeitet Januar 2014. arXiv: 1112.0845

Ich habe auch eine andere verwandte Veröffentlichung von Agol, Hass und Bill Thurston gefunden, in der sie zeigen, dass das allgemeinere Problem der Bestimmung, ob ein Knoten [in einer willkürlich geschlossenen 3-Mannigfaltigkeit] höchstens die Gattung hat, NP-vollständig ist:G

  • Ian Agol, Joel Hass und William Thurston. 3-MANIFOLD KNOT GENUS ist NP-komplett. STOC 2002. ACM-Link

Ich interessiere mich auch für andere Beispiele.

Noam Zeilberger
quelle
3
Der nie veröffentlichte Co-NP-Beweis von Agol unter Verwendung vernähter Hierarchien wird in einer kürzlich durchgeführten Umfrage von Lackenby kurz zusammengefasst: people.maths.ox.ac.uk/lackenby/ekt11214.pdf
Arnaud,
3
R3R3S3
danke für deine präzision: ich habe es in den text aufgenommen.
Noam Zeilberger
2
Vielleicht dicht hier, aber nicht klar, warum die Ergebnisse in der Antwort so charakterisiert sind, dass von Verknotung / Unverknotung gesprochen wird, "NP-hart zu sein", anstatt "in NP zu sein", da sie, soweit ich in der Zusammenfassung sehen kann, behaupten dass die Probleme in NP liegen, aber nicht, dass sie auch NP-vollständig sind.
Abel Molina
1
nein, du hast recht, ich war nur dicht. Jetzt behoben.
Noam Zeilberger