La tesis de Cobham , también conocida como tesis de Cobham-Edmonds (llamada así por Alan Cobham y Jack Edmonds ), [1] [2] [3] afirma que los problemas computacionales pueden calcularse de manera factible en algún dispositivo computacional solo si se pueden calcular en tiempo polinomial ; es decir, si se encuentran en la clase de complejidad P . [4] 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" [5] 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" [6] también se le atribuye la identificación de P con problemas manejables. [7]
Limitaciones
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 100 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 6 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 3 ) a menudo no son prácticos. [9]
Referencias
- ^ Oded Goldreich (2008), Complejidad computacional: una perspectiva conceptual , Cambridge University Press, p. 128, ISBN 978-0-521-88473-0
- ^ Dexter Kozen (2006), Teoría de la computación , Birkhäuser, p. 4, ISBN 978-1-84628-297-3
- ^ Egon Börger (1989), Computabilidad, complejidad, lógica , Elsevier, p. 225, ISBN 978-0-444-87406-1
- ^ Steven Homer y Alan L. Selman (1992), "Complexity Theory" , en Alan Kent y James G. Williams (ed.), Encyclopedia of Computer Science and Technology , 26 , CRC Press
- ^ Alan Cobham (1965), La dificultad computacional intrínseca de las funciones (PDF)
- ^ Edmonds, Jack (1965). "Caminos, árboles y flores". Lata. J. Math . 17 : 449–467. doi : 10.4153 / CJM-1965-045-4 .
- ^ Meurant, Gerard (2014). Algoritmos y complejidad . pag. pag. 4 . ISBN 978-0-08093391-7.
Se dice que un problema es factible si puede resolverse en tiempo polinomial (como se indica por primera vez en Edmonds [26] [1965, Senderos, árboles y flores])).
- ^ D. Pisinger, 2003. "¿Dónde están los problemas de la mochila dura?" Informe técnico 2003/08, Departamento de Ciencias de la Computación, Universidad de Copenhague, Copenhague, Dinamarca, véase [1] Archivado el 23de noviembre de 2015en Wayback Machine , consultado el 31 de enero de 2015.
- ^ Rotman, Brian (18 de junio de 2003). "¿Transformará la computadora digital la matemática clásica?". Phil. Trans. R. Soc. Lond. Una . 361 (1809): 1675–1690. doi : 10.1098 / rsta.2003.1230 . PMID 12952680 .