Problemas de decisión en

¿Cuáles son algunos ejemplos de problemas de decisión difíciles que se pueden resolver en tiempo polinómico? Estoy buscando problemas para los cuales el algoritmo óptimo es "lento", o problemas para los cuales el algoritmo más rápido conocido es "lento".

Aquí hay dos ejemplos:

• Reconocimiento de gráficas perfectas. En su artículo FOCS'03 [1] Cornuéjols, Liu y Vuskovic dieron un algoritmo de tiempo para el problema, donde n es el número de vértices. No estoy seguro de si este límite se ha mejorado, pero según tengo entendido, se necesita más o menos un avance para obtener un algoritmo más rápido. (Los autores dan un algoritmo de tiempo O ( n 9 ) en la versión de revista de [1], ver aquí ).$O(n^{10})$$n$$O(n^9)$

• Reconocimiento de gráficos de mapas. Thorup [2] dio un algoritmo bastante complejo con el exponente siendo (¿aproximadamente?) . Quizás esto se haya mejorado dramáticamente, pero no tengo una buena referencia.$120$

Estoy especialmente interesado en problemas que tienen importancia práctica, y la obtención de un algoritmo "rápido" (o incluso práctico) ha estado abierto durante varios años.

[1] Cornuéjols, Gérard, Xinming Liu y Kristina Vuskovic. "Un algoritmo polinomial para reconocer gráficos perfectos". Fundamentos de Informática, 2003. Actas. 44º Simposio anual de IEEE sobre. IEEE, 2003.

[2] Thorup, Mikkel. "Gráficos de mapas en tiempo polinómico". Fundamentos de Informática, 1998. Actas. 39º Simposio anual sobre. IEEE, 1998.

Quizás los siguientes problemas encajan en sus ejemplos:

• (La versión de decisión de) Colorear, camarilla, conjunto estable, cubierta de camarilla en gráficos perfectos. Hasta ahora, los únicos algoritmos de tiempo polinomiales conocidos para estos problemas se basan en el método elipsoide, que es "lento" (y numéricamente inestable).

• Prueba de primalidad AKS en tiempo . Aunque hay muchas mejoras (actualmente O ( ( log n ) 7.5 ) ), el algoritmo AKS sigue siendo demasiado lento en la práctica.$O((\log n)^{12})$$O((\log n)^{7.5})$

Hay una pregunta similar sobre la teoría , con muchos ejemplos que van desde los algoritmos "realísticamente imprácticamente lentos" con exponentes de 6 o 7 hacia arriba. Esa pregunta también analiza las constantes grandes también.

Hay un clásico que quiero reproducir, ya que parece un ejemplo tan espectacularmente horrible de tiempo polinómico (robado descaradamente de la respuesta de JeffE):

$1752484608000n^{79}L^{25}/D^{26}(\Theta_0)$

$117607251220365312000n^{79}(\ell_{max}/d_{min}(\Theta_0))^{26}.$

De: Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben, James F. O'Brien, Un enfoque impulsado por la energía para el despliegue de enlaces, SOCG 2004.