Gibt es einen Komplexitätsgesichtspunkt des Galois-Theorems?

16
  • Das Theorem von Galois besagt effektiv, dass man die Wurzeln eines Polynoms von Grad> = 5 nicht mit rationalen Funktionen von Koeffizienten und Radikalen ausdrücken kann.

  • Betrachten wir nun eine Entscheidungsfrage der Form: "Wenn ein reelles Wurzelpolynom p und eine Zahl k gegeben sind, ist die dritt- und vierthöchste Wurzel von p mindestens bei einer Lücke von k?"

Ein Beweiszertifikat für diese Entscheidungsfrage wird nur die Menge der Wurzeln dieses Polynoms sein, und das ist ein kurzes Zertifikat, und daher sieht es so aus, als ob NP ABER nicht das Galois-Theorem besagt, dass es keinen deterministischen Algorithmus gibt, um ein Zertifikat dafür zu finden Entscheidungsfrage? (und diese Eigenschaft, wenn true einen Algorithmus ausschließt, um die Antwort auf diese Frage zu bestimmen)

In welcher Komplexitätsklasse liegt diese Entscheidungsfrage?


Alle NP-vollständigen Fragen, die ich gesehen habe, haben immer einen einfachen Exponentialzeitalgorithmus, um sie zu lösen. Ich weiß nicht, ob dies eine Eigenschaft sein soll, die für alle NP-vollständigen Fragen immer zutreffen sollte. Für diese Entscheidungsfrage scheint dies nicht zu stimmen.

user6818
quelle
2
Die Wurzeln sind ein Zertifikat, aber für mich ist es nicht offensichtlich, dass es sich um ein kurzes Zertifikat handelt (dh, dass es eine Konstante so dass Sie für jedes Polynom seine Wurzeln in O ( n k ) Bits ausschreiben können, wobei n ist die Anzahl der Bits, die zum Aufschreiben des Polynoms benötigt werden). Wenn es jedoch einen NP-Algorithmus gibt, gibt es einen trivialen Exponentialzeit-Algorithmus: Zählen Sie einfach alle potenziellen Zertifikate auf und prüfen Sie, ob eines davon funktioniert. kO(nk)n
David Richerby
Ein paar Anmerkungen: (1) Die Wurzeln von haben absolute Werte höchstens max ( 1 , Σ n - 1 i = 0 | a i | / | a n | ) . (2) Sturm-Sequenzen können verwendet werden, um die Wurzeln eines Polynoms zu isolieren. (3) Wir können überprüfen, ob es genau k zwei Wurzeln im Abstand gibt , und wenn ja, welche, indem wir die GCD von p ( x ) und p ( x ) berechnenich=0neinichxichmax(1,ich=0n-1|einich|/|einn|)kp(x) . p(x+k)
Yuval Filmus
@YuvalFilmus Kann eine Ihrer obigen Ideen verwendet werden, um die obige Entscheidungsfrage zu entscheiden? Es ist nicht offensichtlich, ob diese verwendet werden können, um diese Frage zu entscheiden - in polynomialer Zeit?
user6818
1
"Das Theorem von Galois besagt effektiv, dass man die Wurzeln eines Polynoms vom Grad> = 5 nicht mit rationalen Funktionen von Koeffizienten und Radikalen ausdrücken kann - kann man nicht sagen, dass es bei einem gegebenen Polynom keinen deterministischen Algorithmus gibt, um die Wurzeln zu finden? " Nein, da polynomiale Zeitalgorithmen leistungsfähiger sind als rationale Funktionen. Zum Beispiel können sie Fälle teilen, iterieren, Arrays erstellen und eine Schleife über sie erstellen usw.
sdcvvc
2
@ user6818 Der Satz betrifft ein bestimmtes Rechenmodell - rationale Funktionen von Radikalen. Wenn Sie das Modell ändern, gilt es nicht mehr. Zum Beispiel ist es nach MathWorld mathworld.wolfram.com/QuinticEquation.html möglich, die Gleichung 5. Grades mit Jacobi-Theta-Funktionen zu lösen. Wenn Sie sind in Ordnung mit einem Algorithmus, kehrt die Wurzel innerhalb von 0,01 (oder jede beliebigen ), wird die Galois Satz nicht mehr die Methode disqualifizieren, da jede Zahl kann durch eine rationale angenähert werden. ϵ>0
SDCVVC

Antworten:

5

Interessanter Zusammenhang: Die Galois-Theorie besagt jedoch, dass es keine (konsistente) Methode gibt, um mit Radikalen Wurzeln des Quintins zu finden , statt zu sagen, dass das Problem eine Lösung hat (z. B. einen längsten Weg), der möglicherweise Superpolynomzeit erfordert. Ich würde also sagen, dass es eher mit Unentscheidbarkeit als mit Komplexität zu tun hat.

Insbesondere baut man in der Galois-Theorie schrittweise Gruppenerweiterungen der Wurzeln der Gleichung auf (indem man jeweils eine Wurzel hinzufügt). Und alle diese Gruppen sollten lösbar sein, in gewissem Sinne sollte es keine Mehrdeutigkeit beim Aufbau dieser Erweiterungen in einer anderen Reihenfolge geben. Es gibt eine verwandte Frage zu MO zur Komplexität der Konstruktion der Galois-Gruppe einer Gleichung .

Eine weitere Referenz ist hier "COMPUTATIONAL GALOIS THEORY: INVARIANTEN UND RECHNUNGEN ÜBER ", CLAUS FIEKER JURGEN KLUNERSQ.

Darüber hinaus kann man Wurzeln einer Polynomgleichung unter Verwendung von Radikalen (wenn die Gleichung unter Verwendung von Radikalen lösbar ist ) basierend auf der Konstruktion der Galois-Gruppe (n) der Gleichung systematisch darstellen . Ref: "Radikale Darstellung von Polynomwurzeln", Hirokazu Anai Kazuhiro Yokoyama 2002

Die rechnerische Komplexität der Bestimmung, ob ein gegebenes monisch irreduzierbares Polynom über die ganzen Zahlen durch Radikale löslich ist, ist in P Ref "Lösbarkeit durch Radikale in polynomieller Zeit", S. Landau GL Miller 1984ZP

Eine Übersicht über aktuelle "Techniken zur Berechnung von Galois-Gruppen", Alexander Hulpke

Wenn man nach guten Approximationsalgorithmen und ihrer Komplexität sucht (z. B. nach Newtons Methode oder nach Sturm's Theorem), ist dies natürlich eine etwas andere Frage, und die bereits veröffentlichte Antwort liefert mehr Informationen in diese Richtung.

Nikos M.
quelle
Vielen Dank! Scheint, als hätte ich mir aus Versehen eine sehr aufregende Frage gestellt!
user6818
@ user6818, danke aktualisierte Antwort mit mehr Informationen und weiteren Referenzen
Nikos M.
11

Ich gehe davon aus, dass Sie Polynome mit ganzzahligen Koeffizienten betrachten.

Sie haben den falschen Ausgangspunkt für Ihre Ermittlungen gewählt. Ihr Ziel ist es, gute Schätzungen für die realen Wurzeln zu finden. Sie können eine algebraische Formel suchen, damit Sie sie mit ausreichender Genauigkeit auswerten können, aber das ist hier nicht wirklich richtig. (es sei denn natürlich, "die k-th größte echte Wurzel eines Polynoms" ist eine Ihrer algebraischen Operationen)

Ein viel besserer Ausgangspunkt ist die Verwendung des Satzes von Sturm , um die Wurzeln des Polynoms zu isolieren. Sie können dann durch binäre Suche bessere Schätzungen erstellen. Wenn dies jedoch zu langsam ist, können Sie die Newton-Methode verwenden, um schnell Schätzungen mit hoher Genauigkeit zu erstellen.


Aber es geht nur darum , Zertifikate zu finden. Es ist immer noch die Frage, welche Zertifikate existieren können.

Zunächst möchte ich darauf hinweisen, dass Sie direkt berechnen können, ob zwei der Wurzeln genau Einheiten voneinander entfernt sind oder nicht , z. B. indem Sie gcd ( p ( x ) , p ( x - k ) ) berechnen . Sie müssen auch entscheiden, was Sie gegen wiederholte Wurzeln tun möchten, und angemessen damit umgehen. Ich gehe davon aus, dass Sie sich speziell mit diesem Fall befassen werden.kgcd(p(x),p(x-k))

Wenn wir wissen, dass die beiden Wurzeln nicht genau Einheiten voneinander entfernt sind, können Sie eine Schätzung mit ausreichender Genauigkeit erstellen, um zu beweisen, dass sie entweder größer oder kleiner als k Einheiten voneinander entfernt sind. zB gibt es zwei Arten von Zertifikaten:kk

Die erste Art (Beweis im Negativ) ist

  • ist keine Wurzel von peinp
  • hat keine Wurzeln in ( a - k , a )p(ak,a)
  • hat drei Wurzeln in ( a , )p(a,)

Die zweite Art (positiver Beweis) ist

  • ist keine Wurzel von pap
  • hat mindestens zwei Wurzeln in ( a - k , a )p(ak,a)
  • hat zwei Wurzeln in ( a , )p(a,)

Ein Zertifikat kann mit dem Satz von Sturm verifiziert werden. Nun, Ihre Frage über die Größe eines Zertifikats läuft darauf hinaus, zu finden , wie viele Bits der Präzision , die Sie darstellen müssen .a

Mit anderen Worten, wo liegen die Grenzen der möglichen Werte von , wobei a , b Wurzeln von f sind ?abka,bf

Ich bin mir nicht sicher, ob es ein guter Ansatz ist, aber einer, der Ihnen etwas bringen sollte, ist zu beachten, dass all diese Werte Wurzeln des Polynoms sind:

g(x)=Resy(f(y),f(x+y+k))

Warum? Denken Sie daran, dass das Ergebnis zweier monischer Polynome das Produkt aller Unterschiede ihrer Wurzeln ist

g(x)=cd2a,b(b(axk))=a,b(x(abk))

cdfg(x)g(x)

gg

gg


quelle
1
Gibt es hier irgendwelche Probleme bezüglich der Datendarstellung? Bei NP geht es im Wesentlichen um Turing-Maschinen, und es ist nicht sofort ersichtlich, wie sich dies auf reelle Zahlen oder die Anzahl der Bits auswirkt, die erforderlich sind, um Rationen mit ausreichender Genauigkeit aufzuschreiben. (Es tut mir leid, dass ich nicht sehr konstruktiv bin: Ich weiß genug, um zu wissen, dass dies ein Problem sein könnte, aber nicht genug, um zu wissen, ob es wirklich ein Problem ist oder wie man es behebt.)
David Richerby
aa
Die Eingabe als Koeffizientenliste ist sinnvoll. Aber Ihre Annahmen über die Genauigkeit, die zur Darstellung der Wurzeln benötigt wird, müssen auf jeden Fall überprüft werden. Zum Beispiel ist der Grund, warum Hilberts zehntes Problem (das Lösen von Diophantin-Gleichungen) nicht zu entscheiden ist, im Wesentlichen, dass Sie die Länge der Lösung nicht in Bezug auf die Länge der Eingabe begrenzen können. Dies ist hier nicht direkt anwendbar, da wir nur eine Variable haben und nicht nach ganzzahligen Lösungen suchen, aber es stellt eine ziemlich große Frage nach der Annahme der Begrenztheit.
David Richerby
1
@ David: Die Theorie der realen geschlossenen Felder unterscheidet sich dramatisch von der Zahlentheorie. Die Intuition über das eine passt nicht wirklich zum anderen.
k+222nk222n
3

Ich werde Ihre Fragen als meist offen beantworten. Der Galois-Beweis, der jetzt als Abel-Ruffini-Thm bekannt ist, zeigt die Unmöglichkeit polynomieller Lösungen für das Quintin. (im Gegensatz zB zur quadratischen Gleichung). Es ist also nicht wirklich ein Ergebnis der Härte eines Problems an sich, sondern vielmehr der Unmöglichkeit . In diesem Sinne ist es analoger zu z. B. einem Beweis der Unentscheidbarkeit des Halteproblems. Die Komplexitätstheorie befasst sich im Allgemeinen mit den "Kosten" von Computerlösungen. Das ist die Sichtweise von zwei führenden CS-Forschern im Einführungsabschnitt dieses folgenden Artikels ( Berechenbarkeit und Komplexität / Kleinberg & Papadimitriou), Abschnitt 1 Die Suche nach der Quintic-Formel:

Aus der sicheren Entfernung von ein paar Jahrhunderten gesehen handelt es sich eindeutig um eine Rechenstory, die viele der Hauptbestandteile enthält, die bei späteren Berechnungsversuchen entstehen: Wir nehmen einen Rechenprozess, den wir intuitiv verstehen (Lösen einer Gleichung) Formulieren Sie in diesem Fall ein genaues Modell und leiten Sie aus dem Modell einige höchst unerwartete Konsequenzen für die Rechenleistung des Prozesses ab. Genau diesen Ansatz möchten wir auf die Berechnung im Allgemeinen anwenden.

vzn
quelle
Ich bin mir nicht sicher, ob das Stopp-Problem eine gute Analogie ist, da es eher so aussieht wie "Sie können die Antwort nicht berechnen" als wie "es gibt überhaupt keine Antwort".
Ist der Satz von Galois nicht genau wie das Halting-Problem ein rechnerisch unmögliches Ergebnis?
user6818