Gibt es einen Polynomzeitalgorithmus, um herauszufinden, dass die Summe der Quadratwurzeln kleiner als eine ganze Zahl ist?

Gegeben: Eine Liste von$n$ ganze Zahlen $x_1,x_2,\dots,x_n$ und eine ganze Zahl $k$.

Bestimmen: Ist$\sqrt x_1 + \sqrt x_2 \cdots \sqrt x_n \le k$?

Frage: Gibt es einen Polynomzeitalgorithmus für das obige Problem? Wenn ja, geben Sie einen Algorithmus an. sonst beweise es.

Für den Fall, dass Davids Antwort nicht klar ist: Nehmen wir an, Sie haben 10.000 Ganzzahlen $x_i$und k = 1.000.000. Sie können die Quadratwurzeln von n Ganzzahlen einfach mit Gleitkommaoperationen in hinzufügen$O(n)$. Und wenn das Ergebnis 999.999.537 oder 1.000.000.214 lautet, haben Sie die Antwort. Wenn das Ergebnis nahe bei 1.000.000 liegt, können Sie Gleitkomma-Rundungsfehler sehr sorgfältig analysieren. Wenn die Summe 999.999.999999999 lautet, erhalten Sie wahrscheinlich Ihre Antwort. Wenn die Summe zu nahe an k liegt, können Sie mit höherer Genauigkeit rechnen. Abhängig von der genauen Implementierung gibt es also eine Konstante c, sodass Sie die richtige Antwort in finden können$cn$ Zeit für die überwiegende Mehrheit aller Fälle (wenn n wirklich groß ist, dauert es etwas länger, weil die beteiligten Zahlen nur riesig werden, aber dann ist die Zeit sowieso länger als Ihr Leben).

Das Problem ist, dass es Summen von Quadratwurzeln gibt, die sehr, sehr nahe an k kommen können. Beispielsweise können Sie f (x) = Anzahl der Auswahlmöglichkeiten für definieren$x_i$ Wenn die Summe der Quadratwurzeln ≤ x ist, erwarten Sie 2f '(k) * eps Auswahlmöglichkeiten von $x_i$Die Summe der Quadratwurzeln liegt also innerhalb von eps von k entfernt. Sie erwarten eine Kombination, bei der die Summe der Quadratwurzeln innerhalb von eps von k entfernt ist, wenn eps ≥ 1 / 2f '(k) ist. Sie können eine Schätzung dieses EPS berechnen, herausfinden, welche Genauigkeit Ihre Berechnungen benötigen würden, um die richtige Antwort zu erhalten, und wie lange Sie brauchen würden, um das Ergebnis mit dieser Genauigkeit zu erhalten. Dies kann ein Polynom sein oder auch nicht, je nachdem, wie klein das EPS ist.

Aber es ist schlimmer: Was ich oben gesagt habe, ist, wie nahe Sie erwarten , dass eine Summe zu k kommt. Aber es könnte zufällig viel näher sein. Es wäre sehr, sehr schwer zu beweisen, dass es nicht viel näher kommen kann. So kann es sein, dass Sie die Antwort in den meisten Fällen in linearer Zeit finden (> 99,9999999999%), dass Sie erwarten, die Antwort in allen Fällen in Polynomzeit zu finden (oder nicht), aber in jedem Fall können Sie nicht (leicht) beweisen Sie dies, und noch hat es niemand getan.

Es könnte sein, dass Sie die Frage beantworten könnten, ohne die Summe zu berechnen, aber laut David hat auch in der Polynomzeit niemand einen Weg gezeigt, dies zu tun.

Wenn jemand eine Berechnung durchgeführt hat, wie nahe wir erwarten, dass die Summe der Quadratwurzeln einer ganzen Zahl nahe kommt, würde ich mich freuen zu wissen. Übrigens. Ich denke, die Summe der Quadratwurzeln von ganzen Zahlen ist nur dann gleich einer ganzen Zahl, wenn alle Quadratwurzeln ganze Zahlen sind, so dass dies leicht ausgeschlossen werden kann.

PS. Eine grobe Schätzung: Nehmen wir an, wir addieren 10.000 Quadratwurzeln von ganzen Zahlen mit jeweils weniger als 1.000.000. Das sind Quadratwurzeln von$10^{12}$ ganze Zahlen, und da ihre Reihenfolge nicht relevant ist, gibt es etwa $(10^{12})^{10,000} / 10,000!$Summen. Das ist mehr als$10^{80,000}$Summen. Wir erwarten also, dass eine dieser Summen innerhalb liegt$10^{-80,000}$ Abstand zu einer Ganzzahl, die Berechnungen mit einer Genauigkeit von mehr als 80.000 Stellen erfordert.

PS. Bei gegebenen ganzen Zahlen a, b, c, d, k und unter Verwendung der IEEE 754-Arithmetik mit doppelter Genauigkeit ergibt der erste Fall, in dem sqrt (a) + sqrt (b) + sqrt (c) + sqrt (d) <k ein anderes Ergebnis ergibt als Die mathematisch korrekte ist für a, b, c, d = 4640, 5397, 3001, 3322 und k = 254. In diesem Fall wird die Summe als genau 254 berechnet, wenn das mathematische Ergebnis kleiner als 254 ist Das Gleitkomma-Ergebnis entspricht der Ganzzahl. Wir können nicht wissen, ob es aufgerundet oder abgerundet wurde. In diesem Fall hätte dem Ergebnis niemals vertraut werden dürfen.

Mit a, b, c, d = 6222, 8801, 14431, 8132 und k = 383 ist die berechnete Summe größer als k, während das mathematische Ergebnis kleiner ist. Die Reihenfolge der Zahlen spielt keine Rolle, außer dass 14431 die dritte Zahl sein muss.

Wenn wir die Reihenfolge der Operationen durch Hinzufügen von (sqrt (a) + sqrt (b)) + (sqrt (c) + sqrt (d)) ändern (beachten Sie die hinzugefügten Klammern), werden die Rundungsfehler geändert und tendenziell verringert dann ist a, b, c, d = 12558, 407, 16501, 18308 und k = 396 der erste Fall, in dem die berechnete Summe größer als k ist, während das mathematische Ergebnis kleiner ist.

Die Komplexität des Quadratwurzelsummenproblems ist eine seit langem offene Frage . Der Stolperstein ist, dass wir, obwohl wir wissen, wie man Quadratwurzeln effizient berechnet, nicht wissen, ob es möglich ist, festzustellen, ob$\sum_i \sqrt{x_i}\leq k$ durch Auswerten nur einer Polynomzahl von Bits jeder Quadratwurzel.

Das spezifische Problem mit dem Algorithmus, den Sie in der Frage vorschlagen, besteht darin, dass der Ausdruck "Berechnen der Quadratwurzel jedes Werts" nicht spezifiziert ist. Jede irrationale Quadratwurzel (z.$\sqrt{2}$) erfordert die Berechnung einer unendlichen Anzahl von Bits, daher müssen Sie angeben, welche Genauigkeit Sie verwenden.