¿Ejemplos de problemas donde los algoritmos exponenciales se ejecutan más rápido que los algoritmos polinómicos para tamaños prácticos?

13

¿Conoce algún problema (preferiblemente al menos algo bien conocido), donde, para un tamaño de problema práctico , un algoritmo exponencial se ejecuta mucho más rápido que una contraparte de tiempo polinomial más conocida.

Por ejemplo, suponga que un problema tiene un tamaño práctico * de y hay dos algoritmos conocidos: uno es 2 ny el otro es n c para alguna constante c . Claramente para cualquier c > 15 , se prefiere el algoritmo exponencial.n=1002nnccc>15

* Supongo que el tamaño práctico significaría algo que se encuentra comúnmente en el mundo real. Como la cantidad de trenes en una red.

Ozzah
fuente
1
Creo que puede encontrar lo que busca en la literatura de complejidad parametrizada.
Kaveh
Para los algoritmos lineales, generalmente hay un multiplicador constante que generalmente no es significativo y a menudo se omite de la complejidad, pero recuerdo que parecía muy alto fue una fusión en el lugar que era lineal, pero en el peor de los casos algo así como 5000 N ... así que en en ese escenario, hay un área utilizable grande donde N ^ 2 sería menor que 5000 N donde el tamaño es menor que sqrt (5000) y un dominio más pequeño donde 2 ^ n aún sería más rápido donde n es menor que log 5000
Grady Player

Respuestas:

13

¿Qué tal el algoritmo simplex para programación lineal? En muchas ocasiones se usa en la práctica.

Editado para agregar: creo que es más un "algoritmo exponencial en el peor de los casos" que se ejecuta de manera eficiente en instancias prácticas / distribuciones en lugar de ejecutarse más rápido en instancias adversas de tamaño práctico .

RB
fuente
44
@diesalbla: depende de la formalización exacta. Citando Wikipedia, "en 1972, Klee y Minty [32] dieron un ejemplo que muestra que la complejidad del método simplex en el peor de los casos formulada por Dantzig es el tiempo exponencial".
RB
12

O(n3)

Peter Shor
fuente
55
2222|H|O(n3)H
1
O(n2)|H|
1
Hsol|HEl |
-3

Hay algunos ejemplos con detección / prueba de primalidad (no probabilística / exacta) . El algoritmo AKS fue el primer algoritmo para la prueba de primalidad que se mostró en P. No compite favorablemente en comparación con algunos algoritmos de tiempo exponencial para entradas "pequeñas". Los detalles son algo complicados porque mostrar esto generalmente requiere implementar los algoritmos, lo cual es un ejercicio desafiante y puede depender de aspectos específicos de la implementación.

Más información / detalles / referencias sobre esta pregunta cs.se:

vzn
fuente
66
Hasta donde sé, los algoritmos con los que AKS compite en la práctica son polinomios aleatorios (Miller-Rabin, ECPP) o cuasipolinomios deterministas (Adleman-Pomerance-Rumeley). En ninguna parte cerca del tiempo exponencial.
Emil Jeřábek apoya a Monica el
66
La versión aleatorizada de Miller-Rabin, que es la que se usa en la práctica, no depende de la HR.
Emil Jeřábek apoya a Monica el
55
Todo eso es muy cierto, pero no tiene nada que ver con la pregunta original.
Emil Jeřábek apoya a Monica el
2
Sí, sé todo eso. Y por tercera vez, esto es irrelevante. La pregunta pide algoritmos de tiempo exponencial que sean competitivos en la práctica con un algoritmo de tiempo polinomial conocido (aquí, AKS). El único algoritmo de prueba de primalidad de tiempo exponencial utilizado en la práctica es la división de prueba, que no es competitiva para números de cualquier tamaño no trivial. Los algoritmos competitivos utilizados en la práctica son mucho más eficientes que los exponenciales, a pesar de que no son polinomiales (ni deterministas o incondicionales).
Emil Jeřábek apoya a Monica el
3
Lo que son manzanas y naranjas es comparar AKS (un algoritmo de prueba de primalidad) con GNFS (un algoritmo de factorización).
Emil Jeřábek apoya a Monica el