Beweis für die obere Grenze der Summe der Quadratwurzelprobleme

In [1] haben Garey et al. Identifizieren Sie das, was später als das Problem der Summe der Quadratwurzeln bekannt wird, während Sie die NP-Vollständigkeit des euklidischen TSP erarbeiten.

Bestimmen Sie bei gegebenen ganzen Zahlen $a_1, a_2, \ldots, a_n$ und $L$ , ob $\sqrt{a_1} + \sqrt{a_2} + \cdots + \sqrt{a_n} < L$

Sie stellen fest, dass es nicht einmal offensichtlich ist, dass dieses Problem in NP liegt, da nicht klar ist, welche Mindestziffern für die Berechnung der Quadratwurzeln erforderlich sind, um die Summe ausreichend mit $L$ zu vergleichen . Sie zitieren jedoch eine bekannteste Obergrenze von $O(m2^n)$ wobei $m$ "die Anzahl der Stellen im ursprünglichen symbolischen Ausdruck" ist. Leider wird diese Obergrenze lediglich einer persönlichen Mitteilung von AM Odlyzko zugeschrieben.

Hat jemand einen richtigen Verweis auf diese Obergrenze? In Ermangelung einer veröffentlichten Referenz wäre auch ein Beweis oder eine Beweisskizze hilfreich.

Anmerkung: Ich glaube, dass diese Grenze als Folge allgemeinerer Ergebnisse von Bernikel et al. al. [2] ab etwa 2000 Trennungsgrenzen für eine größere Klasse von arithmetischen Ausdrücken. Ich interessiere mich hauptsächlich für zeitgemäßere Referenzen (dh was um 1976 bekannt war) und / oder Beweise, die sich nur auf den Fall der Summe der Quadratwurzeln spezialisiert haben.

Garey, Michael R., Ronald L. Graham und David S. Johnson. " Einige NP-vollständige geometrische Probleme ." Vorträge des achten jährlichen ACM-Symposiums zur Theorie des Rechnens. ACM, 1976.
Burnikel, Christoph et al. " Eine starke und leicht berechenbare Trennung für arithmetische Ausdrücke mit Radikalen ." Algorithmica 27.1 (2000): 87 & ndash; 99.

reference-request cg.comp-geom na.numerical-analysis mhum
quelle

Siehe auch die Antwort auf diese Frage zu cstheory.stackexchange , in der es heißt: "Der bemerkenswerteste Fortschritt in Richtung dieses Problems ist von Eric Allender und seinen Co-Autoren. 2003 haben sie gezeigt, dass dieses Problem in der 4. Ebene der Zählhierarchie liegt. Ftp. cs.rutgers.edu/pub/allender/slp.pdf "

Neal Young

Antworten:

$S = \sum_{i=1}^n \delta_i \sqrt{a_i}$ $\delta_i \in \{\pm 1\}$ $2^n$ $H = (max(a_i))^{n}$ $S = 0$ $TC^0$ $S \neq 0$ $0$ $S$ $a_i$ $2^n$ $S$ $\sqrt{a_i}$ $2^{10n}$ $S$

Nikhil
quelle

Abgestimmt, weil der einzige Teil dieser langen Antwort, der sich tatsächlich mit der Frage befasst, die letzte Zeile ist und es sich um eine Referenz aus dem Jahr 1992 handelt, nicht aus den 1970er Jahren oder früher.

David Eppstein

@david Ich habe nur versucht, eine Beweisskizze dafür zu liefern, warum wir 2 ^ n-Bit-Genauigkeit für die Bewertung der Quadratwurzeln benötigen (@mhum hat irgendwann danach gefragt). Ich bin nicht vertraut damit, wie eine solche Bindung früher vor dem von mir zitierten Artikel abgeleitet wurde (obwohl ich vermute, dass ähnliche Techniken verwendet werden sollten).

Nikhil

Vielleicht bin ich es nur, aber wenn eine Frage lautet: "Ich weiß, wie ich das beweisen kann, aber kann mir jemand eine Referenz geben?", Finde ich Antworten, die zeigen, wie ich es als irritierend beweisen kann. Es ist so, als würden Studenten einer Prüfung eine Antwort auf etwas anderes geben als das, was gefragt wurde, in der Hoffnung (vergeblich), dass sie teilweise Anerkennung dafür erhalten, dass sie etwas wissen, obwohl sie nicht wussten, was Sie von ihnen wollten.

David Eppstein

Ich weiß nicht, woher Sie zitieren, aber es gibt ein "Hat jemand einen richtigen Verweis auf diese Obergrenze? Oder, wenn kein veröffentlichter Verweis vorliegt, wäre auch ein Beweis oder eine Beweisskizze hilfreich." Irgendwo in der Frage

Nikhil

Dies scheint mir plausibel nah genug an dem zu sein, was in der persönlichen Mitteilung hätte sein können. Vielen Dank. (Ich nehme an, ich hätte versuchen können, Odlyzko direkt zu kontaktieren, um es herauszufinden)

mhum