¿Por qué el tiempo polinómico se llama "eficiente"?

50

¿Por qué en informática cualquier complejidad que sea polinomial se considera eficiente?

Para cualquier aplicación práctica (a) , los algoritmos con complejidad son mucho más rápidos que los algoritmos que se ejecutan en el tiempo, por ejemplo, , pero el primero se considera ineficiente mientras que el segundo es eficiente. ¿Dónde está la lógica? n 80nlognn80

(a) Suponga, por ejemplo, que el número de átomos en el universo es aproximadamente .1080

Sonó.
fuente
3
No estoy seguro de estar de acuerdo con su premisa. Creo que la mayoría de la gente consideraría que es bastante ineficiente (aunque, por supuesto, eso también depende de las constantes y del problema que se está resolviendo). n80
sepp2k
16
Consideraría para cualquier muy ineficiente. Tienes un ejemplo de análisis asintótico llevado a un extremo irrazonable. No hay algoritmos naturales (que yo sepa) con tiempo de ejecución. Sin embargo, existen algoritmos naturales con de tiempo de ejecución para algunos problemas, y preguntas fundamentales en la teoría de la complejidad sobre si existe un algoritmo polinómico para tales problemas. c > 3ncc>3 2 nn802n
Joe
55
Creo que esta pregunta no debería ser rechazada porque las personas no están de acuerdo con la premisa (suponiendo que esa fuera la razón). Se supone que los votos hacia arriba y hacia abajo son una indicación de la calidad de la pregunta, no de su contenido (siempre que estén sobre el tema).
Alex ten Brink
8
@Sonó. y la cita completa es (énfasis mío): la tesis de Cobham sostiene que P es la clase de problemas computacionales que son "eficientemente solucionables" o "manejables"; en la práctica, algunos problemas que no se sabe que están en P tienen soluciones prácticas, y algunos que están en P no, pero esta es una regla práctica útil.
Joe
66
En la literatura (de CS teórica), la palabra "eficiente" es sinónimo de "polinomio". Tal vez esto sea diferente para otros subcampos (más prácticos).
Ran G.

Respuestas:

32

Otra perspectiva sobre la "eficiencia" es que el tiempo polinómico nos permite definir una noción de "eficiencia" que no depende de los modelos de máquina. Específicamente, hay una variante de la tesis de Church-Turing llamada "Tesis de Church-Turing efectiva" que dice que cualquier problema que se ejecute en tiempo polinómico en un tipo de modelo de máquina también se ejecutará en tiempo polinómico en otro modelo de máquina igualmente potente.

Esta es una afirmación más débil de la tesis general de CT, y es 'algo así' violada por los algoritmos aleatorios y los algoritmos cuánticos, pero no se ha violado en el sentido de ser capaz de resolver un problema NP-difícil en el tiempo múltiple cambiando El modelo de la máquina.

Esta es, en última instancia, la razón por la cual el tiempo polinomial es una noción popular en teoría CS. Sin embargo, la mayoría de las personas se dan cuenta de que esto no refleja la "eficiencia práctica". Para más información sobre esto, la publicación de Dick Lipton sobre ' algoritmos galácticos ' es una gran lectura.

Suresh
fuente
15
Una segunda razón pragmática para elegir P es que se cierra por adición, multiplicación y exponenciación con constantes. Esto es conveniente al componer algoritmos / máquinas; Si los bloques de construcción son eficientes, también lo es el resultado.
Raphael
Tengo curiosidad, ¿alguien sabe si el término "algoritmo galáctico" se utiliza alguna vez en la práctica?
Juan Bermejo Vega
No es un término tan antiguo. Pero he comenzado a usarlo :)
Suresh
24

En teoría, nos preocupamos por el comportamiento asintótico y describimos clases de problemas y algoritmos basados ​​en su comportamiento asintótico. La palabra clave aquí es asintótica . es más rápido que asintóticamente, es decir, a partir de (que por cierto se llama: septillion!), Suponiendo coeficientes constantes de la unidad, y no bajo -terminos de pedido.O ( n log n ) n > 1208925819614629174706176O(n80)O(nlogn)n>1208925819614629174706176

En la práctica, sin embargo, se presta atención tanto a los exponentes como a los coeficientes constantes. En las prácticas, los tamaños de entrada no pueden crecer hasta septillones, por lo que sí, para todos los propósitos será una opción superior a . Otros factores también son importantes en las prácticas: paralelismo, patrones de acceso a la memoria (por ejemplo, localidad). n 80nlognn80

Por ejemplo, la mayoría de las bibliotecas para la multiplicación de enteros, por ejemplo, GMP implementará una mezcla de algoritmos, y seleccionará un algoritmo inferior basado en el tamaño de entrada, seleccionará los algoritmos prácticamente superiores basados ​​en el tamaño de entrada, aunque estos algoritmos podrían ser asintóticamente inferiores. Algunos algoritmos asintóticamente "inferiores" serán más rápidos en ciertos tamaños de entrada y se seleccionarán sobre los algoritmos óptimos.

Otro ejemplo, el algoritmo de multiplicación matricial más rápido conocido es el algoritmo Coppersmith-Winograd que se ejecuta en (hay mejoras recientes; más aquí ). Sin embargo, nunca se implementó porque (1) es difícil (2) el coeficiente constante es gigantesco. Todos los paquetes de álgebra lineal utilizan el menos óptimo de Strassen .O(n2.3737)

La teoría TL; DR se preocupa por el comportamiento asintótico con el fin de comparar algoritmos a medida que el límite del tamaño de entrada va a números arbitrariamente grandes.


fuente
Ellos "seleccionan algoritmo inferior"? ¿No te refieres a "seleccionar algoritmo superior"?
máscara de bits
Otro buen ejemplo es la ordenación por inserción frente a la ordenación rápida. La ordenación por inserción es mientras que la ordenación rápida es . Sin embargo, en entradas pequeñas, digamos 10 elementos, ¡la ordenación por inserción es aproximadamente el doble de rápida que la ordenación rápida! De hecho, la ordenación rápida optimizada utiliza la ordenación por inserción para matrices pequeñas. O ( n l g n )Θ(N2)O(nlgn)
Robert S. Barnes
¿Por qué no consideramos que los algoritmos asintóticamente cúbicos sean "malos" y los algoritmos asintóticamente cuadráticos "buenos"? Esta respuesta plantea la pregunta.
djechlin
2

Esta respuesta analizará el contexto de "panorama general" de su pregunta. La informática es en realidad una ciencia relativamente joven y algo abierta, y todavía no tiene buenas o buenas respuestas a algunas preguntas básicas y fundamentales. La pregunta básica "qué se calcula eficientemente" se formaliza de manera precisa o aproximada en CS (según la opinión) como el famoso problema P vs NP (o el problema P vs Exptime estrechamente relacionado), y todavía está abierto después de más de cuatro décadas de inicialmente presentado por Cook / Levin ~ 1970 y el intenso trabajo de los mejores informáticos del mundo (y muchos matemáticos también están interesados ​​en el problema como fundamental).

En otras palabras, incluso con una definición aproximada de "eficiente" como tiempo P, y uno de los premios científicos más valorados, es decir, un premio de $ 1M asociado al problema durante más de 10 años, la informática ni siquiera puede probar que algunos problemas (cerca de este límite) debe o no tener algoritmos eficientes (Ptime). Por lo tanto, la definición exacta de "eficiente" más precisa que el tiempo P no es necesaria o incluso posible en este momento. Si / cuando la conjetura P vs NP se resuelve de una forma u otra, una definición más estricta de "eficiente" puede ser o probablemente sea posible.

Además, uno podría sentir que la definición de Ptime de "eficiente" podría incluso ser un poco "descuidada", y la mayoría de los científicos informáticos probablemente estarían de acuerdo, y casi todos piensan que la conjetura P vs NP es de suma importancia para resolver, para el punto de que incluso podrían considerar esta afirmación u observación como trivial ... en otras palabras, por así decirlo, es un trabajo en progreso / estamos trabajando en ello . (de hecho, los científicos informáticos convencionales incluso van tan lejos, solo en tono de broma, para referirse rutinariamente a la brecha y la falta de progreso / separaciones definitivas como vergonzoso ).

De hecho, incluso hay una conjetura estrechamente relacionada / significativamente más fuerte que P vs NP, concretamente NP vs P / poly, que tampoco puede ser resuelta por la informática en este momento. Conjetura que los problemas de tiempo NP no pueden ser resueltos por ningún circuito "tamaño P", es decir, ni siquiera restringido a aquellos circuitos que pueden ser creados por algoritmos / máquinas de Turing.

En cuanto a P lo difícil vs NP puede ser - hay alguna razón de peso para pensar que puede ser al menos tan duro como el muy antigua conjetura de Riemann en matemáticas (ahora 1.5 siglo de edad), ya que ambos han tenido el mismo premio $ 1 M durante más de una década, y ninguno ha sido resuelto todavía / primero.

En otras palabras, definir con precisión qué algoritmos son realmente "eficientes" es en realidad uno de los problemas abiertos más importantes y difíciles existentes en la ciencia teórica y las matemáticas .

De hecho, la cuestión de "qué se computa de manera eficiente" es en realidad aún más sutil, porque hay una variante de la tesis de Church-Turing llamada tesis CT del tiempo P, y no se sabe si la computación cuántica realmente la viola . Con el resultado revolucionario de Shor de P-time QM, el factoring consideró un giro dramático en esta investigación. En otras palabras, el problema de lo que se computa eficientemente en realidad desciende de manera plausible a principios de física profunda, y se relaciona con si la computación cuántica puede computar de manera más eficiente que la computación clásica, que también es un problema generalmente abierto en CS teórica y física avanzada.

Entonces, incluso se puede agregar que P vs NP y la cuestión de la computación eficiente puede ser de importancia crucial o fundamental para, además de CS y las matemáticas, la física .

[1] Problema P vs NP, wikipedia

[2] Problemas con el premio Millenium

[3] Clase P / Poly, wikipedia

[4] Algoritmo de Shor

vzn
fuente
corrección: P vs Pspace, no P vs ExpTime
vzn
-2

Los algoritmos de tiempo polinómico se consideran eficientes solo en comparación con el tiempo no polinomial más difícil, especialmente el denominado NP-Completo. Ver imagen: diagrama de Euler para el conjunto de problemas P, NP, NP completo y NP difícil .

Guillermo A Pussetto
fuente
1
"en comparación con el tiempo no polinomial más difícil, especialmente el llamado NP-Complete": no se sabe que los problemas NP-complete sean no polinomiales, y ciertamente no son los más difíciles.
Raphael