Prova do problema do limite superior da soma das raízes quadradas

Em [1], Garey et al. identificar o que mais tarde seria conhecido como o Problema da Soma das Raízes Quadradas no decurso da conclusão da PN do Euclidean TSP.

Dados os números inteiros e , determine se$a_1, a_2, \ldots, a_n$$L$$\sqrt{a_1} + \sqrt{a_2} + \cdots + \sqrt{a_n} < L$

Eles observam que nem sequer é evidente que este problema está em NP, uma vez que não está claro o que os dígitos mínimos de precisão são necessários no cálculo das raízes quadradas para suficientemente comparar a soma de $L$ . No entanto, eles citam um limite superior mais conhecido de $O(m2^n)$ que $m$ é "o número de dígitos na expressão simbólica original". Infelizmente, esse limite superior é atribuído apenas a uma comunicação pessoal de AM Odlyzko.

Alguém tem uma referência adequada a esse limite superior? Ou, na ausência de uma referência publicada, uma prova ou esboço de prova também seria útil.

Nota: Acredito que esse limite possa ser inferido como consequência de resultados mais gerais de Bernikel et. al. [2], por volta de 2000, nos limites de separação para uma classe maior de expressões aritméticas. Estou interessado principalmente em referências mais contemporâneas (ou seja, o que era conhecido por volta de 1976) e / ou em provas especializadas apenas no caso da soma das raízes quadradas.

1. Garey, Michael R., Ronald L. Graham e David S. Johnson. " Alguns problemas geométricos NP-completos ." Anais do oitavo simpósio anual da ACM sobre Teoria da Computação. ACM, 1976.

2. Burnikel, Christoph et al. " Uma separação forte e facilmente computável destinada a expressões aritméticas envolvendo radicais ". Algorithmica 27.1 (2000): 87-99.

Aqui está um esboço de prova bastante desleixado. Deixe que . Este é um número algébrico de grau no máximo e altura no máximo . Agora, é fácil verificar se (pode ser feito mesmo em - veja isso ). Se então ele é limitado a partir de por uma quantidade (porque é um número algébrico e, portanto, é raiz diferente de zero de um polinômio univariado) que é uma função do grau e altura do polinômio mínimo de$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≠00Sai2nS√$S \neq 0$$0$$S$. Infelizmente, a dependência do grau é exponencial no número de raízes quadradas (e se os são primos distintos, esse limite de grau é ainda rígido, embora seja fácil lidar com esse caso de avaliação de sinais). A precisão necessária é, portanto, exponencial do número de raízes quadradas, que é -bits para . Agora basta truncar cada um dos para dizer$a_i$$2^n$$S$$\sqrt{a_i}$$2^{10n}$bits para garantir que o sinal esteja correto. Isso é feito facilmente através de várias etapas polinomialmente da iteração de Newton). Agora cabe verificar se a soma é positiva, que é apenas adição e, portanto, linear no número de bits nos summands. Observe que esse cálculo ocorre no tempo polinomial em uma máquina BSS. Observe também que não estamos fazendo nenhum cálculo diretamente com o polinômio mínimo do próprio , que pode ter enormes coeficientes e parecer feio, apenas o usamos para raciocinar sobre a precisão com a qual precisamos truncar as raízes quadradas. Para mais detalhes, consulte o artigo de Tiwari .$S$