¿Existe un punto de vista de complejidad del teorema de Galois?

El teorema de Galois dice efectivamente que no se pueden expresar las raíces de un polinomio de grado> = 5 usando funciones racionales de coeficientes y radicales. ¿No se puede leer que esto dice que dado un polinomio no hay un algoritmo determinista para encontrar las raíces?
Ahora considere una pregunta de decisión de la forma, "Dado un polinomio con raíz real $p$ y un número k es la tercera y la cuarta raíz más alta de $p$ al menos en una brecha de k?"

Un certificado de prueba para esta pregunta de decisión solo será el conjunto de raíces de este polinomio y ese es un certificado corto y, por lo tanto, parece que $NP$ PERO no es el teorema de Galois que dice que no existe ningún algoritmo determinista para encontrar un certificado para este pregunta de decisión? (y esta propiedad si es verdadera descarta cualquier algoritmo para decidir la respuesta a esta pregunta)

Entonces, ¿en qué clase de complejidad se encuentra esta pregunta de decisión?

Todas las preguntas NP-complete que he visto siempre tienen un algoritmo de tiempo exponencial trivial disponible para resolverlas. No sé si se espera que esto sea una propiedad que siempre debería ser cierta para todas las preguntas de NP-complete. Para esta pregunta de decisión esto no parece ser cierto.

complexity-theory np-complete np polynomials usuario6818
fuente

Las raíces son un certificado, pero no es obvio para mí que son un certificado corto (es decir, que hay una constante

k

$k$ tal que, para cada polinomio, puede escribir sus raíces en bits

O (n^{k})

$O(n^k)$ , donde

n

$n$ es el número de bits necesarios para escribir el polinomio). Pero si hay un algoritmo NP, hay un algoritmo trivial de tiempo exponencial: simplemente enumere todos los certificados potenciales y vea si alguno de ellos funciona.

David Richerby

\sum_{i = 0}^{n} a_{i} x_{i}

$\sum_{i=0}^n a_i x_i$

max (1, \sum_{i = 0}^{n - 1} | a_{i} | / | a_{n} |)

$\max(1,\sum_{i=0}^{n-1} |a_i|/|a_n|)$

k

$k$

p (x)

$p(x)$

p (x + k)

$p(x+k)$

@YuvalFilmus ¿Se puede utilizar alguna de las ideas anteriores para decidir la pregunta de decisión anterior? No es obvio si se pueden usar para decidir esta pregunta, ¿en tiempo polinómico?

usuario6818

"El teorema de Galois dice efectivamente que no se pueden expresar las raíces de un polinomio de grado> = 5 usando funciones racionales de coeficientes y radicales. ¿No se puede leer que esto dice que dado un polinomio no hay un algoritmo determinista para encontrar las raíces? " No, dado que los algoritmos de tiempo polinomiales son más poderosos que las funciones racionales. Por ejemplo, se puede dividir los casos, iterate, crear matrices y bucle sobre ellos etc.

sdcvvc

@ user6818 El teorema se refiere a un modelo de cálculo específico: funciones racionales de radicales. Si cambia el modelo, ya no se aplica. Por ejemplo, de acuerdo con MathWorld mathworld.wolfram.com/QuinticEquation.html es posible resolver la ecuación de 5º grado usando las funciones theta de Jacobi. Si está bien con un algoritmo que devuelve la raíz dentro de 0.01 (o cualquier

), el teorema de Galois ya no descalificará el método, ya que cualquier número puede ser aproximado por un racional.

ϵ > 0

$\epsilon > 0$

sdcvvc

Respuestas:

Una conexión interesante, sin embargo, la teoría de Galois afirma que no existe un método (consistente) para encontrar raíces de quintic usando radicales , en lugar de decir que el problema tiene una solución (por ejemplo, un camino más largo) que puede requerir un tiempo superpolinomial. Entonces diría que está más relacionado con la indecidibilidad que con la complejidad.

Específicamente, en la teoría de Galois se construyen progresivamente extensiones de grupo de las raíces de la ecuación, paso a paso (agregando una raíz a la vez). Y todos estos grupos deberían poder resolverse, en cierto sentido no debería haber ambigüedad en el proceso de construcción de estas extensiones en otro orden. Hay una pregunta relacionada sobre MO sobre la complejidad de construir el grupo de Galois de una ecuación .

Otra referencia aquí "TEORÍA DE GALOIS COMPUTACIONAL: INVARISTAS Y COMPUTACIONES SOBRE ", CLAUS FIEKER JURGEN KLUNERS $\mathbb{Q}$

Además, uno puede representar sistemáticamente las raíces de una ecuación polinómica usando radicales (cuando la ecuación se puede resolver usando radicales) basándose en la construcción del grupo o grupos de Galois de la ecuación. Ref: "Representación radical de las raíces polinomiales", Hirokazu Anai Kazuhiro Yokoyama 2002

La complejidad computacional de determinar si un polinomio irreducible monico dado sobre los enteros , es soluble por radicales está en Ref "La solubilidad por radicales está en tiempo polinómico", S. Landau GL Miller 1984 $\mathbb{Z}$ $\mathbb{P}$

Una encuesta de las "Técnicas para la computación de los grupos de Galois" recientes, Alexander Hulpke

Por supuesto, si uno está buscando buenos algoritmos de aproximación y su complejidad (por ejemplo, el método de Newton o el Teorema de Sturm), esta es una pregunta ligeramente diferente y la respuesta ya publicada proporciona más información en esa dirección.

Nikos M.
fuente

¡Gracias! ¡Parece que accidentalmente me hice una pregunta muy emocionante!

user6818

@ user6818, gracias respuesta actualizada con más información y referencias adicionales

Nikos M.

Supongo que está considerando polinomios con coeficientes enteros .

Has tomado el punto de partida equivocado para tus investigaciones; Su objetivo es encontrar buenas estimaciones para las raíces reales. Buscar una fórmula algebraica para poder evaluarla con suficiente precisión es algo que puede hacer, pero en realidad no es lo correcto. (a menos que, por supuesto, "la kenésima raíz real más grande de un polinomio" sea una de sus operaciones algebraicas)

Un punto de partida mucho mejor es usar el teorema de Sturm para aislar las raíces del polinomio. Luego puede producir mejores estimaciones mediante búsqueda binaria, pero si es demasiado lento, puede usar el método de Newton para producir rápidamente estimaciones de alta precisión.

Pero se trata solo de encontrar certificados. Todavía queda la cuestión de qué certificados pueden existir.

En primer lugar, señalaré que puede calcular directamente si dos de las raíces están separadas exactamente por unidades, por ejemplo, calculando . También tendrá que decidir qué quiere hacer con respecto a las raíces repetidas y tratarlas adecuadamente. Supongo que tratarás este caso especialmente. $k$ $\gcd(p(x), p(x-k))$

Si sabemos que las dos raíces no están exactamente separadas por unidades, eso significa que puede producir una estimación de precisión suficiente para demostrar que son mayores o menores que unidades separadas. Por ejemplo, hay dos tipos de certificados: $k$ $k$

El primer tipo (prueba en negativo) es

no es una raíz de $a$ $p$
no tiene raíces en $p$ $(a-k, a)$
tiene tres raíces en $p$ $(a, \infty)$

El segundo tipo (prueba en positivo) es

no es una raíz de $a$ $p$
tiene al menos dos raíces en $p$ $(a-k,a)$
tiene dos raíces en $p$ $(a, \infty)$

Se puede verificar un certificado utilizando el teorema de Sturm. Ahora, su pregunta sobre el tamaño de un certificado se reduce a encontrar cuántos bits de precisión necesita para representar . $a$

En otras palabras, ¿cuáles son los límites de los posibles valores de , donde son raíces de ? $a-b-k$ $a,b$ $f$

No estoy seguro de un gran enfoque, pero uno que debería darle algo es observar que todos estos valores son raíces del polinomio:

g (x) = {Res}_{y} (f (y), f (x + y + k))

$g(x) = \mathop{\text{Res}_y}(f(y), f(x + y + k))$

¿Por qué? Recuerde que la resultante de dos polinomios monicos es el producto de todas las diferencias de sus raíces, por lo que

g (x) = c^{d^{2}} \prod_{a, b} (b - (a - x - k)) = \prod_{a, b} (x - (a - b - k))

$g(x) = c^{d^2} \prod_{a,b}(b - (a - x - k)) = \prod_{a,b} (x - (a-b-k))$

donde es el coeficiente principal es el grado de . (tal vez he escrito la fórmula para lugar de ; nunca estoy seguro del signo) $c$ $d$ $f$ $-g(x)$ $g(x)$

$g$ $g$

fuente

¿Hay algún problema con la representación de datos aquí? NP trata fundamentalmente de las máquinas de Turing y no es obvio de inmediato cómo se relaciona con los números reales o la cantidad de bits necesarios para anotar los racionales con suficiente precisión. (Lamento no ser muy constructivo: sé lo suficiente como para saber que esto podría ser un problema, pero no lo suficiente como para saber si realmente es un problema o, si lo es, cómo volver a resolverlo.)

David Richerby

a

$a$

a

$a$

La entrada como una lista de coeficientes tiene mucho sentido. Pero sus suposiciones sobre la precisión necesaria para representar las raíces definitivamente deben verificarse. Por ejemplo, la razón por la cual el décimo problema de Hilbert (resolver ecuaciones de diofantina) es indecidible es esencialmente que no se puede vincular la longitud de la solución en términos de la longitud de la entrada. Eso no es directamente aplicable aquí, ya que solo tenemos una variable y no estamos buscando soluciones enteras, pero sí hace una pregunta bastante importante sobre el supuesto de acotación.

David Richerby

@David: La teoría de los campos cerrados reales es dramáticamente diferente a la teoría de números; la intuición acerca de uno realmente no se traduce bien al otro.

k + 2^{- 2^{2^{n}}}

$k+2^{-2^{2^n}}$

k - 2^{- 2^{2^{n}}}

$k-2^{-2^{2^n}}$

Voy a tomar sus preguntas como mayormente abiertas. la prueba de galois ahora conocida como Abel-Ruffini thm muestra la imposibilidad de soluciones polinómicas a la quíntica. (en contraste con, por ejemplo, la ecuación cuadrática). así que no es realmente un resultado de la dureza de un problema per se sino más bien la imposibilidad . en este sentido, es más análogo a, por ejemplo, una prueba de indecidibilidad del problema de detención. La teoría de la complejidad se refiere en general al "costo" de las soluciones informáticas. ese es el punto de vista de dos investigadores de CS líderes en la sección introductoria de este artículo ( Computability and Complexity / Kleinberg & Papadimitriou), sec 1 La búsqueda de la fórmula quíntica:

Vista desde una distancia segura de unos pocos siglos, la historia es claramente una sobre la computación, y contiene muchos de los ingredientes clave que surgen en los esfuerzos posteriores para modelar la computación: tomamos un proceso computacional que entendemos intuitivamente (resolviendo una ecuación , en este caso), formule un modelo preciso, y del modelo derive algunas consecuencias altamente inesperadas sobre el poder computacional del proceso. Es precisamente este enfoque el que queremos aplicar a la computación en general.

en otra parte, una analogía general / general podría ser que una P $\neq$ La prueba NP (u otra separación de clase de complejidad) es análoga a un resultado de imposibilidad computacional algo similar al Abel-Ruffini thm. un resultado de separación dice aproximadamente que los problemas de cierto tipo no pueden resolverse con "recursos computacionales" de otro cierto tipo. una P $\neq$ El teorema de NP se vería como un resultado de imposibilidad computacional (monumental).

vzn
fuente

No estoy seguro de que el problema de detención sea una buena analogía, ya que está más en la línea de "no se puede calcular la respuesta" en lugar de "no hay una respuesta en absoluto".

¿No es el teorema de Galois un resultado de imposibilidad computacional como el problema de detención?

user6818