Ist P= NP in zellulärer Automaten von hyperbolischen Räumen?

Question

Ich habe vor ein paar Jahren in dieses Buch das NP-Probleme sind im Raum von zellulären Automaten in der hyperbolischen Ebene traktbar. Was bedeutet das? Ist P = NP gemäß diesen Büchern / Papieren?

Einige Auszüge aus dem Papier:

Es ist allgemein bekannt, dass, wenn wir Binärbäume zur Verfügung haben, "KOSTENLOS" haben, es möglich ist, NP-Probleme bei der Polynomzeit zu lösen, siehe [14, 5]. Es ist jedoch nicht sofortig, binäre Baumalgorithmen in Pentagrid zu implementieren, und das Ziel dieses Abschnitts ist es, anzugeben, wie man fortgesetzt wird.

aus meinem Verständnis, dem p= np Problem sucht nach Polynom-Zeit-Algorithmen bis lösen komplizierte Probleme. Von meinem flusswürdigen Blick durch die Bücher und Papiere scheint es vorzuschlagen, dass er das Problem gelöst hat. Was vermisse ich?

hier ist ein anderes Papier mit dem Titel in einigen gebogenen Räumen, wir Kann NP-harte Probleme bei der Polynomzeit lösen: in Richtung Matiyasevichs Traum .

Answer 1

Das P-NP-Problem ist eine Frage zu Turing-Maschinen $ T $ , da die Komplexitätsklassen P und NP in Bezug auf diese theoretischen Maschinen definiert sind. Nennen wir diese Klassen $ p_t $ und $ np_t $ ab sofort ein. Das Papier stellt einen neuen theoretischen Berechnungsmaschinen ein, der $ H $ inklusive klassen $ p_h $ (läuft in Polynom Zeit auf dem hyperbolischen Mobiltelefon-Automaton) und $ np_h $ (läuft in nicht deterministischer Polynomzeit auf dem hyperbolischen Zellularautomaton).

Der erste Schritt in diesem Papier ist ein Beweis dafür, dass das 3SAT-Problem, ein bekanntes Problem -Komponenten-"-Komponenten-Problem, in dieser Maschine in der Polynomialzeit gelöst werden kann , dh dieses Problem ist in $ p_h $ . Als nächstes zeigen sie, dass die Polynom-Zeitreduzierung auf einer Turingmaschine in der Polynomzeit auf ihrem hyperbolischen Automaton durchgeführt werden kann. Da 3sat $ NP_T $ -competen ist, kann jeder $ NP_T $ instanz auf eine 3sat-Instanz reduziert werden Polynomzeit (auf $ t $ per Definition, also auch auf $ H $ von ihrem Lemma) und dann durch Lösen von 3sat in Poly-Time, sowohl auf dem hyperbolischen Automaton, gelöst werden. Mit anderen Worten, das Hauptergebnis dieses Papiers (Satz 1) kann als $ NP_T \ Subseteq p_h $ in unserer Notation geschrieben werden. Dies ergibt keine Lösung für das P-NP-Problem, da dies den Klassen $ NP_T $ und in Verbindung müsste $ P_t $ .

Beachten Sie, dass die Autoren einige Anmerkungen zum P-Vs. NP-Problem in Abschnitt 4.2 enthalten, in denen sie das Ergebnis behaupten, dass das Ergebnis für P $ \ neq $ NP ist ( !):

Eine dritte Richtung besteht aus dem neuen Lichtschuppen auf der P= NP-Frage in der gewöhnliche Einstellungen. Da der hyperbolische Raum Eigenschaften aufweist, die sich insbesondere von den Eigenschaften des euklidischen Raums unterscheiden, hat es insbesondere noch viele weitere Richtungen, wären dies nicht, dass dies ein Hinweis ist, um diesen P $ \ zu beweisen neq $ np bei euklidischen Bedingungen? Es scheint, dass In den letzten zehn Jahren neigen die Werke auf dem Gebiet der Komplexität, die die Menschen glauben Mehr in P $ \ neq $ np. Anscheinend gehört das vorliegende Ergebnis auch zu diesem Trend.