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

9

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 a1,a2,,an i Lokreśl, czy a1+a2++an<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(m2n) gdzie mto „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.

mum
źródło
1
Zobacz także odpowiedź na to pytanie cstheory.stackexchange , które brzmi: „Najbardziej niezwykły postęp w kierunku tego problemu dokonał Eric Allender i jego współautorzy, w 2003 roku wykazali, że ten problem leży na 4 poziomie Counting Hierarchy. Ftp. cs.rutgers.edu/pub/allender/slp.pdf "
Neal Young,

Odpowiedzi:

7

Oto raczej niechlujny szkic próbny. PozwolićS=i=1nδiai gdzie δi{±1}. Jest to co najwyżej liczba algebraiczna2n i co najwyżej wysokość H=(max(ai))n. Teraz łatwo jest sprawdzić, czyS=0 (można to zrobić nawet w TC0- zobacz to ). jeśliS0 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śliaisą 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, czyli2n-bity na S. Wystarczy teraz obciąć każdy z nichai powiedzieć 210nbity, 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 wielomianuSsama 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 .

Nikhil
źródło
Głosowane, ponieważ jedyną częścią tej długiej odpowiedzi, która faktycznie dotyczy tego pytania, jest ostatnia linia i jest to odniesienie z 1992 r., A nie z lat 70. lub wcześniej.
David Eppstein,
2
@david Właśnie próbowałem przedstawić szkic dowodu, dlaczego potrzebujemy 2 ^ n-bitowej precyzji do oceny pierwiastków kwadratowych (@mhum poprosił o nią w pewnym momencie). Nie znam sposobu, w jaki taka granica została wyprowadzona wcześniej przed cytowanym przeze mnie artykułem (choć podejrzewam, że powinna ona stosować podobne techniki).
Nikhil
Może to tylko ja, ale kiedy pytanie brzmi: „Wiem, jak to udowodnić, ale czy ktoś może dać mi referencję”, znajduję odpowiedzi pokazujące, jak udowodnić, że jest to irytujące. To tak, jakby uczniowie na egzaminie udzielali odpowiedzi na coś innego niż to, o co zostali poproszeni, mając nadzieję (na próżno), że uzyskają częściowe uznanie za wiedzę, nawet jeśli nie wiedzieli, czego chcesz.
David Eppstein,
8
Nie wiem, skąd zacytowałeś, ale pojawia się pytanie „Czy ktoś ma odpowiednie odniesienie do tej górnej granicy? Lub, w przypadku braku opublikowanego odniesienia, pomocny byłby również szkic lub dowód”. Gdzieś w pytaniu
Nikhil
Wydaje mi się to wystarczająco zbliżone do tego, co mogło być w osobistej komunikacji. Dzięki. (Przypuszczam, że mogłem spróbować skontaktować się bezpośrednio z Odlyzko, żeby się dowiedzieć)
mhum,