Algoritmos de tiempo polinómico con gran exponente / constante

¿Conoce algoritmos sensibles que se ejecutan en tiempo polinómico en (Longitud de entrada + longitud de salida), pero cuyo tiempo de ejecución asintótico en la misma medida tiene un exponente / constante realmente enorme (al menos, donde el límite superior probado en el tiempo de ejecución está en de tal forma)?

Los algoritmos basados ​​en el lema de regularidad son buenos ejemplos de algoritmos de tiempo polinómico con constantes terribles (ya sea en el exponente o como coeficientes iniciales).

El lema de regularidad de Szemeredi le dice que en cualquier gráfico en vértices puede dividir los vértices en conjuntos donde los bordes entre pares de conjuntos son "pseudoaleatorios" (es decir, las densidades de subconjuntos suficientemente grandes se parecen a densidades en un gráfico aleatorio) . Esta es una estructura con la que es muy agradable trabajar, y como consecuencia hay algoritmos que usan la partición. El problema es que el número de conjuntos en la partición es una torre exponencial en el parámetro de pseudoaleatoriedad (Ver aquí: http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma ).$n$

Para ver algunos enlaces a algoritmos que dependen del lema de regularidad, consulte, por ejemplo: http://www.cs.cmu.edu/~ryanw/regularity-journ.pdf

Noticias de SODA 2013 : el problema de la bisección máxima es aproximado dentro de un factor 0.8776 en aproximadamente .$O(n^{10^{100}})$

Aquí hay dos capturas de pantalla de An Energy-Driven Approach to Linkage Unfolding de Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben, James F. O'Brien, SOCG 2004:

Aquí hay un resultado reciente de la edición de 2012 FUN Picture-Hanging Puzzles de Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph SB Mitchell, Ronald L. Rivest y Mihai Patrascu.

Mostramos cómo colgar una imagen envolviendo la cuerda alrededor de n clavos, haciendo un número polinómico de giros, de modo que la imagen se cae cada vez que se quita cualquier k de las n uñas, y la imagen permanece colgando cuando se quitan menos de k clavos.

No dejes que el 'número polinómico' te engañe ... resulta ser .$O(n^{43737})$

Existe una clase de problemas, cuyas soluciones son difíciles de calcular, pero es fácil aproximarlas a cualquier precisión , en el sentido de que existen algoritmos de tiempo polinomial que pueden aproximar la solución dentro para cualquier constante ε > 0. Sin embargo, hay un problema: el tiempo de ejecución de los aproximadores puede depender bastante de , por ejemplo, ser .1 / ϵ O ( n 1 / ϵ$(1+\epsilon)$$1/\epsilon$$O(n^{1/\epsilon})$

Ver más información aquí: http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme .

Aunque el tiempo de ejecución para tales algoritmos se ha mejorado posteriormente, el algoritmo original para muestrear un punto de un cuerpo convexo tenía tiempo de ejecución .$\tilde{O}(n^{19})$

Dyer, Frieze y Kannan: http://portal.acm.org/citation.cfm?id=102783

Si es una lógica modal o superintucionista tabular, entonces los sistemas de prueba de Frege y sustitución de Frege extendidos para son polinomialmente equivalentes y polinomialmente fielmente interpretables en el EF clásico (este es el Teorema 5.10 en este trabajo mío). El exponente de las simulaciones polinómicas no se establece explícitamente en el Teorema 5.10, pero la prueba inductiva del teorema da , donde es un marco de Kripke finito que genera , por lo que puede ser tan grande como quieras dependiendo de la lógica. (Empeora en el Teorema 5.20.)L c c = 2 O ( | F | ) F $L$$L$$c$$c=2^{O(|F|)}$$F$$L$

El algoritmo más conocido actual para reconocer gráficos de mapas (una generalización de gráficos planos) se ejecuta en . Thorup, Gráficos de mapas en tiempo polinómico.$n^{120}$

Calcular el equilibrio del mercado Arrow-Debreu requiere cálculos de flujo máximo de , donde es la utilidad máxima. Duan, Mehlhorn, un algoritmo polinómico combinatorio para el mercado lineal Arrow-Debreu.$O(n^6\log(nU))$$U$

Problema de fugacidad de pila de arena

Considere el siguiente proceso. Tome un azulejo grueso y deje caer partículas de arena sobre él un grano a la vez. Un montón se acumula gradualmente y luego una gran porción de arena se desliza desde los bordes de la baldosa. Si continuamos agregando partículas de arena, después de un cierto punto de tiempo, la configuración del montón se repite. A partir de entonces, la configuración se vuelve recurrente, es decir, sigue revisando un estado que se vio anteriormente.

Considere el siguiente modelo para el proceso anterior. Modele el mosaico como una cuadrícula . Se dejan caer partículas de arena en los vértices de esta cuadrícula. Si el número de partículas en un vértice excede su grado, entonces el vértice colapsa y las partículas en él se mueven a vértices adyacentes (en cascada). Una partícula de arena que alcanza un vértice límite desaparece en un sumidero ("se cae"). Esto se conoce como el modelo Abelian Sandpile .$n \times n$

Problema: ¿Cuánto tiempo tarda la configuración en volverse recurrente en términos de , suponiendo el peor algoritmo para soltar partículas de arena?$n$

En SODA '07 , László Babai e Igor Gorodezky demostraron que esta vez estaban polinómicamente limitados pero ...

En SODA '12 , Ayush Choure y Sundar Vishwanathan mejoraron este límite a .$O(n^7)$

Esta respuesta se habría visto un poco mejor si no fuera por su mejora :)

El problema del "cráneo convexo" es encontrar el polígono convexo de área máxima dentro de un polígono simple dado. El algoritmo más rápido conocido para este problema se ejecuta en tiempo [Chang y Yap, DCG 1986].$O(n^7)$

La solución de los Juegos de aniquilación (Fraenkel y Yesha) tiene complejidad .$O(n^6)$

Existen algunos algoritmos no constructivos, en particular el teorema de Fellows y Langston y Courcelle .

Además, el algoritmo de tiempo lineal de Bodlaender para el ancho de árbol y el teorema de Courcelle son notoriamente poco prácticos.

El teorema de Robertson-Seymour, también conocido como Teorema del grafo menor, establece, entre otras cosas, que para cualquier gráfico , existe un algoritmo que determina si un gráfico arbitrario (de tamaño ) tiene como menor. La prueba no es constructiva y la constante multiplicativa (creo que no es uniforme) es probablemente tan enorme que no se puede escribir explícitamente una fórmula (por ejemplo, como una función recursiva primitiva en ).$G$$O(n^3)$$H$$n$$G$$G$

http://en.wikipedia.org/wiki/Graph_minor_theorem#Polynomial_time_recognition

En su artículo de ICALP 2014 , Andreas Björklund y Thore Husfeldt dan el primer algoritmo polinomial (aleatorio) que calcula 2 rutas disjuntas con una longitud total mínima (suma de la longitud de las dos rutas) entre dos pares de vértices dados. El tiempo de ejecución está en .$O(n^{11})$

En la rectificación de polígonos, parte 2: Número mínimo de rectángulos gruesos , se presenta una modificación práctica del problema de partición de rectángulos motivada por preocupaciones en VLSI:

Optimización de la grasa del rectángulo Problema: Dado un polígono ortogonal , maximizar el menor lado sobre todas rectangulations de . Entre las particiones con el mismo , elija la partición con el menor número de rectángulos.$P$$\delta$$P$$\delta$

Hasta el momento, solo existe un algoritmo teórico, con un tiempo de ejecución de . (Eso no es un error tipográfico, y se obtiene a través de una solución de programación dinámica "natural" para el problema allí mencionado).$O(n^{42})$

calcular la rigidez de la matriz [1] a través de la fuerza bruta / ingenua / enumeraciones aparentemente lleva tiempo para matrices de tamaño elementos. Esto puede verse como un límite convergente de una secuencia de estimaciones cada vez más precisas que toman , , , ... pasos. en otras palabras, cada estimación está en tiempo P para cualquier exponente arbitrario (es decir, pasos). el algoritmo ingenuo elige cualquier$O(2^n)$$n$$n \choose 1$$n \choose 2$$n \choose 3$$O(n^c)$$c$$n \choose c$$c$elementos de la matriz para cambiar y pruebas para la reducción de dimensión resultante. Esto no es totalmente sorprendente dado que se ha relacionado con los límites inferiores del circuito informático. esto sigue un patrón en el que muchos algoritmos tienen una solución de tiempo P conjeturada para algún parámetro, pero una prueba sólida de un límite inferior probablemente implicaría o algo más fuerte.$\mathsf{P \neq NP}$

[1] Preguntas sobre la rigidez de la matriz informática

Sorprendentemente, una de las respuestas más obvias aún no publicada. encontrar una camarilla de tamaño (bordes o vértices) aparentemente lleva tiempo mediante el algoritmo de fuerza bruta / ingenua que enumera todas las posibilidades. o más exactamente proporcional a pasos. (curiosamente, este hecho básico parece ser raramente señalado en la literatura). Sin embargo, una prueba estricta de ello implicaría . entonces esta pregunta está relacionada con la famosa conjetura abierta, prácticamente equivalente a ella. otros problemas de tipo NP pueden parametrizarse de esta manera.$c$$O(n^c)$$n \choose c$$\mathsf{P \neq NP}$