Tesis de Cobham - Cobham's thesis

La tesis de Cobham , también conocida como tesis de Cobham-Edmonds (llamada así por Alan Cobham y Jack Edmonds ), afirma que los problemas computacionales pueden calcularse de manera factible en algún dispositivo computacional sólo si pueden computarse en tiempo polinomial ; es decir, si se encuentran en la clase de complejidad P . En términos modernos, identifica problemas tratables con la clase de complejidad P .

Formalmente, decir que un problema se puede resolver en tiempo polinomial es decir que existe un algoritmo que, dada una instancia de n bits del problema como entrada, puede producir una solución en el tiempo O ( n ^c ), la letra O es notación de orden O y c es una constante que depende del problema pero no el caso particular del problema.

El artículo de 1965 de Alan Cobham titulado "La dificultad computacional intrínseca de las funciones" es una de las primeras menciones del concepto de la clase de complejidad P , que consiste en problemas decidibles en tiempo polinomial. Cobham teorizó que esta clase de complejidad era una buena manera de describir el conjunto de problemas viables computables .

Al artículo de 1965 de Jack Edmonds, "Senderos, árboles y flores", también se le atribuye la identificación de P con problemas manejables.

Limitaciones

El gráfico muestra el tiempo de solución del problema en milisegundos (ms) frente al tamaño del problema, n, para problemas de mochila resueltos por un algoritmo especializado de última generación utilizando una computadora Pentium III a 933 MHz (promedio de 100 instancias, datos de :). El ajuste de la ecuación cuadrática sugiere que la complejidad algorítmica empírica para instancias con 50 a 10,000 variables es O ((log  n ) ² ) a pesar de tener una estimación exponencial de la complejidad del peor de los casos en teoría.

Si bien la tesis de Cobham es un hito importante en el desarrollo de la teoría de la complejidad computacional , tiene limitaciones cuando se aplica a la viabilidad práctica de los algoritmos. La tesis esencialmente establece que " P " significa "fácil, rápido y práctico", mientras que "no en P " significa "difícil, lento y poco práctico". Pero esto no siempre es cierto, porque la tesis abstrae algunas variables importantes que influyen en el tiempo de ejecución en la práctica:

• Ignora factores constantes y términos de orden inferior.
• Ignora el tamaño del exponente. El teorema de la jerarquía temporal demuestra la existencia de problemas en P que requieren exponentes arbitrariamente grandes.
• Ignora el tamaño típico de la entrada.

Los tres están relacionados y son quejas generales sobre el análisis de algoritmos , pero se aplican particularmente a la tesis de Cobham, ya que hace una afirmación explícita sobre la practicidad. Según la tesis de Cobham, un problema para el que el mejor algoritmo toma n ²⁰⁰ instrucciones se considera factible, y un problema con un algoritmo que toma 2 ^{0.00001 n} instrucciones no es factible, aunque nunca se podría resolver una instancia de tamaño n = 2 con el algoritmo anterior. , mientras que un ejemplo del último problema de tamaño n = 10 ⁶ podría resolverse sin dificultad. En campos donde los problemas prácticos tienen millones de variables (como la Investigación de Operaciones o la Automatización del Diseño Electrónico ), incluso los algoritmos O ( n ³ ) a menudo no son prácticos.

Referencias