Preuve du problème de la limite supérieure de la somme des racines carrées

Dans [1], Garey et al. identifier ce qui serait plus tard connu sous le nom de problème de la somme des racines carrées au cours de l'élaboration de l'exhaustivité NP du TSP euclidien.

Étant donné les entiers $a_1, a_2, \ldots, a_n$ et $L$ , déterminez si $\sqrt{a_1} + \sqrt{a_2} + \cdots + \sqrt{a_n} < L$

Ils observent qu'il est même pas évident que ce problème est dans NP car on ne sait pas ce que les chiffres minimums de précision sont requis dans le calcul des racines carrées de suffisamment comparer la somme à $L$ . Cependant, ils citent une borne supérieure la plus connue de $O(m2^n)$ où $m$ est "le nombre de chiffres dans l'expression symbolique d'origine". Malheureusement, cette limite supérieure n'est attribuée qu'à une communication personnelle de AM Odlyzko.

Quelqu'un at-il une référence appropriée à cette limite supérieure? Ou, en l'absence d'une référence publiée, une épreuve ou un croquis d'épreuve serait également utile.

Remarque: Je pense que cette limite pourrait être déduite à la suite de résultats plus généraux de Bernikel et. Al. [2] à partir d'environ 2000 sur les limites de séparation pour une plus grande classe d'expressions arithmétiques. Je suis surtout intéressé par des références plus contemporaines (ie: ce qui était connu vers 1976) et / ou des preuves spécialisées uniquement au cas de la somme des racines carrées.

1. Garey, Michael R., Ronald L. Graham et David S. Johnson. " Quelques problèmes géométriques NP-complets ." Actes du huitième symposium annuel de l'ACM sur la théorie de l'informatique. ACM, 1976.

2. Burnikel, Christoph et al. " Une séparation forte et facilement calculable à destination des expressions arithmétiques impliquant des radicaux ." Algorithmica 27.1 (2000): 87-99.

$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$