El Garey y Johnson libro (Equipos y Intractibility: Una Guía para la Teoría de la NP-Completitud, 1979) tiene una explicación detallada de este, temprano. Yo no puedo recomendar lo suficiente.
Hay varias razones por las que los problemas son considerados como "manejable" si tienen polinomio de algoritmos, pero la más importante es esta: Supongamos que usted tiene una computadora y con ella se puede factibles de calcular soluciones para el Widget Problema hasta 10,000 widgets. Su cliente, sin embargo, necesita para resolver los más grandes de los casos, y si usted puede ayudar a ellos, que tendrán que pagar un montón de dinero. Para ayudar a hacer esto, usted tendrá que invertir un poco de la tasa en la actualización de su equipo para el último modelo, que es dos veces tan rápido como su actual equipo.
Si su algoritmo para resolver el Widget Problema es $O(n)$, el nuevo equipo va a resolver instancias de participación de hasta 20,000 widgets, una importante mejora.
Si su algoritmo para resolver el Widget Problema es $O(n^2)$, el nuevo equipo será factible para resolver instancias de participación de hasta 14,142 widgets, también una importante mejora.
Incluso si el algoritmo es $O(n^3)$, será factible para resolver casos relacionados con 12,599 widgets, siendo una mejora significativa.
Pero si el algoritmo es $O(2^n)$, el nuevo equipo permitirá que usted para resolver instancias del Widget Problema con la participación de hasta 10,001 widgets, que es apenas una mejora en absoluto.
Esa es la diferencia entre polinomial y exponencial de los algoritmos.
Estás en lo correcto, que no es precisamente un marcado la brecha entre polinomial y exponencial de los algoritmos. Un polinomio de tiempo de algoritmo que toma $153672n^{537}$ el tiempo es probablemente menos útil en la práctica de una exponencial que lleva la $\frac{1.00001^n}{153672}$ del tiempo. Pero el tipo de algoritmos que aparecen realmente en la práctica no suele ser $O(n^{537})$; por lo general, $O(n^3)$ o mejor. Y también, con respecto a la pregunta 2, cualquier polinomio algoritmo de superar cualquier algoritmo exponencial para suficientemente grande instancias del problema.
Pero sí, hay ejemplos reales de nominalmente exponencial de tiempo de los algoritmos que son lo bastante eficiente como para ser útil en la práctica. El "simplex" algoritmo para el entero de problemas de programación lineal es un ejemplo bien conocido.
