En [1], Garey et al. identifique lo que luego se conocería como el problema de la suma de las raíces cuadradas en el curso de la determinación de la integridad de NP del TSP euclidiano.
Dados los enteros y , determine si
Observan que ni siquiera es evidente que este problema está en NP ya que no está claro lo que se requiere que las cifras mínimas de precisión en el cálculo de las raíces cuadradas de comparar suficientemente la suma de . Sin embargo, sí citan un límite superior más conocido de donde es "el número de dígitos en la expresión simbólica original". Desafortunadamente, este límite superior se atribuye simplemente a una comunicación personal de AM Odlyzko.
¿Alguien tiene una referencia adecuada a este límite superior? O, en ausencia de una referencia publicada, una prueba o un bosquejo de prueba también sería útil.
Nota: Creo que este límite podría inferirse como consecuencia de resultados más generales por Bernikel et. Alabama. [2] de alrededor de 2000 en los límites de separación para una clase más grande de expresiones aritméticas. Estoy interesado principalmente en referencias más contemporáneas (es decir, lo que se sabía alrededor de 1976) y / o pruebas especializadas solo en el caso de la suma de raíces cuadradas.
Garey, Michael R., Ronald L. Graham y David S. Johnson. " Algunos problemas geométricos NP-completos ". Actas del octavo simposio anual de ACM sobre Teoría de la informática. ACM, 1976.
Burnikel, Christoph y col. " Una separación fuerte y fácilmente computable vinculada a expresiones aritméticas que involucran radicales ". Algorithmica 27.1 (2000): 87-99.
Respuestas:
Aquí hay un boceto de prueba bastante descuidado. SeaS= ∑nortei = 1δyounayo--√ dondeδyo∈ { ± 1 } . Este es un número algebraico de grado como máximo2norte y altura como máximoH= ( m a x ( ayo) )norte . Ahora es fácil verificar siS= 0 (se puede hacer incluso enTC0 0 - veaesto). SiS≠0 entonces está limitado desde0 por una cantidad (porque es un número algebraico y por lo tanto es un no-cero de la raíz de un polinomio univariado) que es una función del grado y la altura del polinomio mínimo de S . Por desgracia, la dependencia del grado es exponencial en el número de raíces cuadradas (y si los ai 's son números primos distintos, este grado es obligado incluso apretado, sin embargo, que el caso de la evaluación signo es fácil de manejar). La precisión que se necesita es por lo tanto exponencial en el número de raíces cuadradas, que es 2n -bits para S . Ahora es suficiente para truncar cada uno de los ai−−√ para decir210n bits para garantizar que el signo sea correcto. Esto se hace fácilmente a través de muchos pasos polinomiales de la iteración de Newton). Ahora se trata de verificar si la suma es positiva, que es solo suma y, por lo tanto, lineal en el número de bits en los sumandos. Observe que este cálculo está en tiempo polinómico en una máquina BSS. También tenga en cuenta que no estamos haciendo ningún cálculo directamente con el polinomio mínimo deS sí mismo, que podría tener coeficientes enormes y verse feo, solo lo usamos para razonar sobre la precisión con la que necesitamos truncar las raíces cuadradas. Para más detalles, consulteel artículo de Tiwari.
fuente