¿Por qué el tiempo polinomio se llama “eficiente”?

Question

¿Por qué en la informática cualquier complejidad que es como máximo polinomio se considera eficiente?

Para cualquier aplicación práctica ^(a) , algoritmos con complejidad $ n ^ {\ log n} $ son mucho más rápido que los algoritmos que se ejecutan en el tiempo, por ejemplo, $ n ^ {80} $, pero la primera se considera ineficaz, mientras que el segundo es eficiente. ¿Dónde está la lógica?!

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

Answer 1

Otra perspectiva sobre la "eficiencia" es que el tiempo polinomio nos permite definir una noción de "eficiencia" que no depende de los modelos de máquinas. En concreto, hay una variante de la tesis de Church-Turing llamado el "efectivo Tesis de Church-Turing" que dice que cualquier problema que se ejecuta en tiempo polinómico en el tipo de modelo de máquina también se ejecutarán en tiempo polinómico en otro igualmente poderoso modelo de máquina.

Esta es una declaración más débil de la tesis general de CT, y es 'una especie de' violada por ambos algoritmos aleatorios y algoritmos cuánticos, pero no ha sido violado en el sentido de ser capaz de resolver un problema NP-duro en poli- tiempo cambiando el modelo de máquina.

Esto es en última instancia, la razón por la cual el tiempo polinomio es una noción popular en theoryCS. Sin embargo, la mayoría de las personas se dan cuenta de que esto no refleja la "eficacia práctica". Para más información sobre esto, después de Dick Lipton en ' galáctico algoritmos ' es una gran lectura.

Answer 2

En teoría, cuidamos el comportamiento asintótico, y describimos las clases de problemas y algoritmos basados ??en su comportamiento asintótico. La palabra clave aquí es asintótica . $ O (n ^ {80}) $ es más rápido que $ O (n ^ {\ log n}) $ asintóticamente, es decir, a partir de $ n> 1208925819614629174706176 $ (que por cierto se llama: septillón), unidad que lo coeficientes constantes, y no hay términos de bajo orden.

En la práctica, sin embargo, se presta atención tanto a los exponentes y coeficientes constantes. En las prácticas, los tamaños de entrada no pueden crecer a septillones, así que, sí, $ n ^ {\ log n} $ a todos los efectos será una opción superior a $ n ^ {80} $. Otros factores que también importa en las prácticas:. Paralelismo, los patrones de acceso de memoria (por ejemplo, localidad)

Por ejemplo, la mayoría de las bibliotecas para la multiplicación de enteros, por ejemplo GMP implementará una mezcla de algoritmos, y seleccione algoritmo inferior basado en el tamaño de entrada seleccionar el prácticamente algoritmos superiores basado en el tamaño de entrada, aunque estos algoritmos pueden ser asintótica inferior. Algunos algoritmos asintóticamente "inferiores" habrá más rápido en ciertos tamaños de entrada, y se seleccionará a través de los algoritmos óptimos.

Otro ejemplo, el algoritmo de multiplicación de matrices más rápida conocida es Calderero-Winograd algoritmo que se ejecuta en $ O (n ^ {2,3737}) $ (hay mejoras recientes; más aquí ). Sin embargo, nunca se llevó a cabo debido a que (1) es de (2) el coeficiente constante duro es gigantesca. Todos los paquetes de álgebra lineal utilizan el menos óptimo de Strassen .

TL;. DR cuidados teoría de comportamiento asintótico con el fin de comparar los algoritmos como el límite de tamaño de entrada va a arbitrariamente grandes números

Answer 3

Esta respuesta se verá en el "cuadro grande" contexto de su pregunta. La informática es en realidad una ciencia relativamente joven y algo abierto y que aún no tienen grandes o incluso buenas respuestas a algunas preguntas básicas y fundamentales. La pregunta básica "lo que se calcula de manera eficiente" es o bien con precisión o más o menos formalizado en CS (dependiendo de opinión) como el famoso P vs problema NP (o el estrechamente vinculado P vs. EXPTIME problema), y su todavía abrir después de más de cuatro décadas de ser introducido inicialmente por Cook / Levin ~ 1970 y un intenso trabajo por los mundos más grandes también están interesados ??los informáticos (y muchos matemáticos en el problema como fundamental).

En otras palabras, incluso con un bruto definición de "eficiente" como el tiempo P, y uno de los premios científicos de mayor valor - es decir premio 1M $ adjunta al problema desde hace más de 10 años: - equipo la ciencia ni siquiera puede probar que algunos problemas (cerca de este límite) deben o no deben tener algoritmos eficientes (ptime). Por lo tanto, la definición exacta de "eficiente" tiempo más preciso que P no es necesario, ni siquiera posible en este momento. Si / cuando el P vs NP conjetura se resuelve de un modo u otro, una definición más estricta de "eficiente" puede o presumiblemente será posible.

Por otra parte, uno puede sentir que la definición de ptime de "eficiente" incluso podría ser un poco "descuidado", y la mayoría de los informáticos probablemente estaría de acuerdo, y casi todos ellos pensar que el P vs NP conjetura es de suma importancia para determinación, hasta el punto que incluso podrían considerar esta afirmación u observación tan trivial .... en otras palabras, por así decirlo, es un trabajo en progreso / nosotros estamos trabajando en ello . (De hecho los informáticos corriente incluso ir tan lejos, medio en broma, para referirse de forma rutinaria a la distancia y la falta de progreso / separaciones definitivas como embarazoso .)

De hecho, hay incluso un / significativamente más fuerte conjetura estrechamente relacionado a P vs NP, es decir, NP vs P / poli, que tampoco puede ser resuelto por la informática en este momento. se conjetura que los problemas NP-tiempo no pueden ser resueltos por cualquier circuitos "de tamaño P", es decir, ni siquiera limitado 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 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 tampoco se ha resuelto todavía / primero.

Así, en otras palabras, para definir con precisión lo que los algoritmos son muy "eficiente" es en realidad uno de los problemas abiertos más importantes y más difíciles que existen en la ciencia teórica y matemáticas .

De hecho, la cuestión de "lo que se calcula de manera eficiente" en realidad es aún más sutil, porque hay una variante de la tesis de Church-Turing llamado la tesis CT-P Tiempo, y no se sabe si la computación cuántica en realidad viola ella. Con el resultado de Shor avance de QM P-tiempo, la factorización considera un giro dramático en esta investigación. En otras palabras, el problema de lo que se calcula de manera eficiente en realidad desciende plausiblemente todo el camino a principios de la física de profundidad, y se refiere a si la computación cuántica puede calcular con mayor eficiencia que la computación clásica, que también es un problema general, abierta en CS teórica y la física avanzada.

Así que uno puede incluso añadir que P vs NP y la cuestión de la computación eficiente pueda ser de crucial importancia o fundamental en - además de CS y matemáticas -. la física

[1] P vs problema NP, wikipedia

[2] problemas de premios Millenium

[3] clase P / Poly, wikipedia

[4] de Shor algoritmo

Answer 4

algoritmos de tiempo polinómico se consideran eficientes sólo en comparación con el momento más difícil no es un polinomio en especial el llamado NP-completo. Ver imagen: Euler diagrama para P, NP, NP-completo, y NP-duro conjunto de problemas .