Доказательство для верхней границы суммы квадратов

В [1] Garey et al. определите то, что позже будет известно как проблема суммы квадратных корней в ходе разработки NP-полноты евклидовой TSP.

Даны целые числа $a_1, a_2, \ldots, a_n$ а также $L$определить, если $\sqrt{a_1} + \sqrt{a_2} + \cdots + \sqrt{a_n} < L$

Они отмечают, что даже не очевидно, что эта проблема в NP, так как не ясно, какие минимальные цифры точности требуются при вычислении квадратных корней, чтобы в достаточной мере сравнить сумму с $L$, Тем не менее, они приводят наиболее известную верхнюю границу$O(m2^n)$ где $m$это «количество цифр в исходном символическом выражении». К сожалению, эта верхняя граница объясняется лишь личным общением с А. М. Одлызко.

У кого-нибудь есть правильная ссылка на эту верхнюю границу? Или, в случае отсутствия опубликованной ссылки, доказательство или эскиз доказательства также могут быть полезны.

Примечание: я считаю, что эта граница может быть выведена как следствие более общих результатов, полученных Bernikel et. и др. [2] примерно с 2000 года о границах разделения для большего класса арифметических выражений. В основном меня интересуют более современные ссылки (например, то, что было известно примерно в 1976 году) и / или доказательства, специализирующиеся только на случае суммы квадратных корней.

1. Гэри, Майкл Р., Рональд Л. Грэм и Дэвид С. Джонсон. « Некоторые NP-полные геометрические задачи ». Материалы восьмого ежегодного симпозиума ACM по теории вычислений. ACM, 1976.

2. Burnikel, Christoph, et al. « Сильное и легко вычислимое разделение, связанное с арифметическими выражениями с участием радикалов ». 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}$биты, чтобы гарантировать, что знак гарантированно будет правильным. Это легко сделать с помощью полиномиального множества шагов итерации Ньютона). Теперь дело до проверки, является ли сумма положительной, которая является просто сложением и, следовательно, линейной по количеству битов в слагаемых. Обратите внимание, что это вычисление выполняется за полиномиальное время на машине BSS. Также обратите внимание, что мы не делаем никаких вычислений напрямую с минимальным полиномом$S$Сам по себе, который может иметь огромные коэффициенты и выглядеть уродливо, мы просто используем его, чтобы рассуждать о точности, с которой нам нужно обрезать квадратные корни. Для более подробной информации, проверьте документ Tiwari .