Gibt es einen Komplexitätsgesichtspunkt des Galois-Theorems?

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.

complexity-theory np-complete np polynomials user6818
quelle

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

Bits ausschreiben können, wobei

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.

k

$k$

O (n^{k})

$O(n^k)$

n

$n$

David Richerby

Ein paar Anmerkungen: (1) Die Wurzeln von

haben absolute Werte höchstens

. (2) Sturm-Sequenzen können verwendet werden, um die Wurzeln eines Polynoms zu isolieren. (3) Wir können überprüfen, ob es genau

zwei Wurzeln im Abstand gibt , und wenn ja, welche, indem wir die GCD von

und

berechnen

\sum_{i = 0}^{n} a_{i} x_{i}

$\sum_{i=0}^n a_i x_i$

max (1, \sum_{i = 0}^{n - 1} | a_{i} | / | a_{n} |)

$\max(1,\sum_{i=0}^{n-1} |a_i|/|a_n|)$

k

$k$

p (x)

$p(x)$

p (x + k)

$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

"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

@ 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

$\epsilon > 0$

SDCVVC

Antworten:

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 KLUNERS $\mathbb{Q}$

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 Ref "Lösbarkeit durch Radikale in polynomieller Zeit", S. Landau GL Miller 1984 $\mathbb{Z}$ $\mathbb{P}$

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.

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 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. $k$ $\gcd(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 Einheiten voneinander entfernt sind. zB gibt es zwei Arten von Zertifikaten: $k$ $k$

Die erste Art (Beweis im Negativ) ist

ist keine Wurzel von $a$ $p$
hat keine Wurzeln in $p$ $(a-k, a)$
hat drei Wurzeln in $p$ $(a, \infty)$

Die zweite Art (positiver Beweis) ist

ist keine Wurzel von $a$ $p$
hat mindestens zwei Wurzeln in $p$ $(a-k,a)$
hat zwei Wurzeln in $p$ $(a, \infty)$

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 Wurzeln von ? $a-b-k$ $a,b$ $f$

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) = {Res}_{y} (f (y), f (x + y + k))

$g(x) = \mathop{\text{Res}_y}(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) = c^{d^{2}} \prod_{a, b} (b - (a - x - k)) = \prod_{a, b} (x - (a - b - k))

$g(x) = c^{d^2} \prod_{a,b}(b - (a - x - k)) = \prod_{a,b} (x - (a-b-k))$

$c$ $d$ $f$ $-g(x)$ $g(x)$

$g$ $g$

quelle

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

a

$a$

a

$a$

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

@ David: Die Theorie der realen geschlossenen Felder unterscheidet sich dramatisch von der Zahlentheorie. Die Intuition über das eine passt nicht wirklich zum anderen.

k + 2^{- 2^{2^{n}}}

$k+2^{-2^{2^n}}$

k - 2^{- 2^{2^{n}}}

$k-2^{-2^{2^n}}$

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.

$\neq$ $\neq$

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