Dowód problemu dla górnej granicy sumy pierwiastków kwadratowych

W [1] Garey i in. określić, co później będzie znane jako problem sumy pierwiastków kwadratowych w trakcie opracowywania kompletności NP euklidesowej TSP.

Podane liczby całkowite $a_1, a_2, \ldots, a_n$ i $L$określ, czy $\sqrt{a_1} + \sqrt{a_2} + \cdots + \sqrt{a_n} < L$

Zauważają, że nie jest nawet oczywiste, że problem ten występuje w NP, ponieważ nie jest jasne, jakie minimalne cyfry precyzji są wymagane przy obliczaniu pierwiastków kwadratowych, aby wystarczająco porównać sumę z $L$. Przytaczają jednak najbardziej znaną górną granicę$O(m2^n)$ gdzie $m$to „liczba cyfr w oryginalnym wyrażeniu symbolicznym”. Niestety, ta górna granica jest przypisana jedynie osobistej komunikacji AM Odlyzko.

Czy ktoś ma właściwe odniesienie do tej górnej granicy? Lub, w przypadku braku opublikowanego odniesienia, pomocny byłby również dowód lub szkic.

Uwaga: Uważam, że ograniczenie to można wywnioskować na podstawie bardziej ogólnych wyników Bernikel i in. glin. [2] z około 2000 r. Na temat granic separacji dla większej klasy wyrażeń arytmetycznych. Najbardziej interesują mnie bardziej współczesne odniesienia (tj. Co było znane około 1976 r.) I / lub dowody specjalizujące się w przypadku sumy pierwiastków kwadratowych.

1. Garey, Michael R., Ronald L. Graham i David S. Johnson. „ Niektóre problemy geometryczne pełne NP ”. Materiały z ósmego dorocznego sympozjum ACM na temat teorii obliczeń. ACM, 1976.

2. Burnikel, Christoph i in. „ Silna i łatwa do obliczenia separacja związana z wyrażeniami arytmetycznymi z udziałem rodników ”. Al Algorytmica 27.1 (2000): 87-99.

Oto raczej niechlujny szkic próbny. Pozwolić$S = \sum_{i=1}^n \delta_i \sqrt{a_i}$ gdzie $\delta_i \in \{\pm 1\}$. Jest to co najwyżej liczba algebraiczna$2^n$ i co najwyżej wysokość $H = (max(a_i))^{n}$. Teraz łatwo jest sprawdzić, czy$S = 0$ (można to zrobić nawet w $TC^0$- zobacz to ). jeśli$S \neq 0$ to jest ograniczone $0$ według wielkości (ponieważ jest to liczba algebraiczna, a zatem niezerowy pierwiastek wielomianu jednowymiarowego), który jest funkcją stopnia i wysokości minimalnego wielomianu $S$. Niestety zależność od stopnia jest wykładnicza w liczbie pierwiastków kwadratowych (a jeśli$a_i$są odrębnymi liczbami pierwszymi, ten stopień stopnia jest jeszcze ciasny, chociaż ten przypadek oceny znaku jest łatwy do opanowania). Potrzebna precyzja jest zatem wykładnicza w liczbie pierwiastków kwadratowych, czyli$2^n$-bity na $S$. Wystarczy teraz obciąć każdy z nich$\sqrt{a_i}$ powiedzieć $2^{10n}$bity, aby zagwarantować poprawność znaku. Można to łatwo zrobić poprzez wielomianowo wiele kroków iteracji Newtona). Teraz sprowadza się do sprawdzenia, czy suma jest dodatnia, co jest tylko dodatkiem, a zatem liniową liczbą bitów w sumach. Zauważ, że to obliczenie odbywa się w czasie wielomianowym na maszynie BSS. Zauważ też, że nie wykonujemy żadnych obliczeń bezpośrednio przy minimalnym wielomianu$S$sama w sobie, która może mieć ogromne współczynniki i wyglądać brzydko, po prostu używamy jej do uzasadnienia precyzji, do której musimy obciąć pierwiastki kwadratowe. Aby uzyskać więcej informacji, sprawdź artykuł Tiwari .