Tesis de Cobham

En ciencias de la computación, la tesis de Cobham, también conocida como la tesis de Cobham-Edmonds (llamada así por Alan Cobham y Jack Edmonds)^[2][3][4] afirma que los problemas tratables o "fácilmente computables" son los problemas computables en tiempo polinómico. En particular, los problemas de decisión “fácilmente” computables son los de clase P .

El gráfico muestra el tiempo en milisegundos para resolver instancias del problema de la mochila en función del tamaño de entrada n. El experimento se realizó en una computadora Pentium III de 933 MHz (los datos son de un promedio de más de 100 instancias cada vez^[1] ).

Esta tesis es importante porque la clase P es precisamente una clase que no es sensible a los detalles de un modelo computacional; por ejemplo, una máquina de Turing de una o varias bandas da la misma definición de la clase P.

El artículo de Alan Cobham (1965) se llama La dificultad computacional intrínseca de las funciones y es una de las primeras apariciones de la clase P, que consiste en problemas decidibles en tiempo polinómico. Cobham teorizó que esta clase de complejidad era una buena forma de describir el conjunto de problemas factiblemente computables. Al artículo de Jack Edmonds de 1965 "Caminos, árboles y flores" ^[5] también se le atribuye la identificación de P con problemas tratables.

^[6]

Esta tesis ha sido criticada porque no tiene en cuenta el exponente del polinomio en absoluto, pero según el teorema de la jerarquía temporal determinista, existen problemas cuyo mejor algoritmo tiene un exponente arbitrariamente grande.

Notas y referencias

1. D. Pisinger, 2003. "Where are the hard knapsack problems?" Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark, see, accessed 31 January 2015.
2. Oded Goldreich (2008). [Tesis de Cobham, p. 128, en Google Libros Computational complexity] |url= incorrecta (ayuda) (en inglés). Cambridge: Cambridge University Press. p. 128 |página= y |páginas= redundantes (ayuda). ISBN 978-0-521-88473-0.
3. Dexter Kozen (2006). [Tesis de Cobham, p. 4, en Google Libros Theory of computation] |url= incorrecta (ayuda) (en inglés). Londres: Birkhäuser. p. 4 |página= y |páginas= redundantes (ayuda). ISBN 978-1-84628-297-3.
4. Egon Börger (1989). [Tesis de Cobham, p. 225, en Google Libros Computability, complexity, logic] |url= incorrecta (ayuda) (en inglés). Amsterdam/New York/New York, N.Y., U.S.A: Elsevier. p. 225. ISBN 978-0-444-87406-1..
5. Edmonds, Jack (1965). «Paths, trees, and flowers». Can. J. Math. 17: 449-467. doi:10.4153/CJM-1965-045-4.
6. Meurant, Gerard (2014). Algorithms and Complexity. p. p. 4. ISBN 978-0-08093391-7. «A problem is said to be feasible if it can be solved in polynomial time (as stated for the first time in Edmonds [26] [1965, Paths, trees, and flowers])).»

• Datos: Q5138877