Prueba de problema de límite superior de suma de raíces cuadradas

9

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 sia1,a2,,anorteLa1+una2++unanorte<L

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.LO(metro2norte)metro

¿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.

  1. 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.

  2. 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.

mhum
fuente
1
Vea también la respuesta a esta pregunta cstheory.stackexchange , que dice: "El progreso más notable hacia este problema es por Eric Allender y sus coautores, en 2003, mostraron que este problema se encuentra en el 4to nivel de la Jerarquía de Conteo. Ftp. cs.rutgers.edu/pub/allender/slp.pdf "
Neal Young

Respuestas:

7

Aquí hay un boceto de prueba bastante descuidado. Sea S=yo=1norteδyounayo dondeδyo{±1}. Este es un número algebraico de grado como máximo2nortey altura como máximoH=(metrounaX(unayo))norte. Ahora es fácil verificar siS=0 0(se puede hacer incluso enTC0 0- veaesto). SiS0entonces está limitado desde0por 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 decir210nbits 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 deSsí 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.

Nikhil
fuente
Votó en contra porque la única parte de esta larga respuesta que realmente aborda la pregunta es la última línea, y es una referencia de 1992, no de la década de 1970 o antes.
David Eppstein
2
@david Solo estaba tratando de proporcionar un bosquejo de prueba de por qué necesitamos una precisión de 2 ^ n bits para evaluar las raíces cuadradas (@mhum lo solicitó en algún momento). No estoy familiarizado con cómo se derivó tal límite antes del artículo que cité (aunque sospecho que debería usar técnicas similares).
Nikhil
Tal vez soy solo yo, pero cuando una pregunta dice "Sé cómo probar esto, pero ¿alguien puede darme una referencia?", Encuentro respuestas que muestran cómo demostrar que es irritante. Es como cuando los estudiantes en un examen dan una respuesta a algo diferente de lo que se les preguntó, con la esperanza (en vano) de que obtengan un crédito parcial por saber algo a pesar de que no sabían lo que querían.
David Eppstein
8
No sé de dónde está citando, pero hay un "¿Alguien tiene una referencia adecuada a este límite superior? O, en ausencia de una referencia publicada, una prueba o bosquejo de prueba también sería útil". En algún lugar de la pregunta
Nikhil
Esto me parece plausiblemente lo suficientemente cerca de lo que podría haber sido en la comunicación personal. Gracias. (Supongo que podría haber intentado ponerse en contacto Odlyzko directamente para averiguar)
mhum