Tesis de CobhamEn 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 . 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
|