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

¿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 $n^{\log n}$$n^{80}$

^{(a) Suponga, por ejemplo, que el número de átomos en el universo es aproximadamente .$10^{80}$}

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.

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 > $O(n^{80})$$O(n^{\log n})$$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 $n^{\log n}$$n^{80}$

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(n^{2.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.

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

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 .