Tesis de Cobham
En ciències de la computació, la tesis de Cobham, també coneguda com la tesis de Cobham-Edmonds (cridada aixina per Alan Cobham i Jack Edmonds)[2][3][4] afirma que els problemes tractables o "fàcilment computables" són els problemes computables en temps polinòmic. En particular, els problemes de decisió “fàcilment” computables són els de classe P .
Esta tesis és important perque la classe P és precisament una classe que no és sensible als detalls d'un model computacional; per eixemple, una màquina de Turing d'una o vàries bandes dona la mateixa definició de la classe P.
L'artícul d'Alan Cobham (1965) es diu La dificultat computacional intrínseca de les funcions i és una de les primeres aparicions de la classe P, que consistix en problemes decidibles en temps polinòmic. Cobham teorizó que esta classe de complexitat era una bona forma de descriure el conjunt de problemes factiblemente computables. A l'artícul de Jack Edmonds de 1965 "Camins, arbres i flors" [5] també se li atribuïx l'identificació de P en problemes tractables.
Esta tesis ha segut criticada perque no té en conte l'exponent del polinomi en absolut, pero segons la teorema de la jerarquia temporal determinista, existixen problemes el millor algoritme dels quals té un exponent arbitrariamente gran.
Notes i referències
[editar | editar còdic]- ↑ D. Pisinger, 2003. "Where llaure the hard knapsack problems?" Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark, see, accessed 31 January 2015.
- ↑ Oded Goldreich (2008). Computational complexity (en en), Cambridge: Cambridge University Press, p. 128. ISBN 978-0-521-88473-0.
- ↑ Dexter Kozen (2006). Theory of computation (en en), Londres: Birkhäuser, p. 4. ISBN 978-1-84628-297-3.
- ↑ Egon Börger (1989). Computability, complexity, logic (en en), Amsterdam/New York/New York, N.Y., U.S.A: Elsevier, p. 225. ISBN 978-0-444-87406-1..
- ↑ (1965).Ca. J. Math..17
- 449–467.doi:10.4153/CJM-1965-045-4.
- ↑ Meurant (2014). Algorithms and Complexity, p. p. 4. ISBN 978-0-08093391-7. «A problem is said to be feasible if it ca be solved in polynomial clave (as stated for the first clave in Edmonds [26] [1965, Paths, trees, and flowers])).»
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Tesis de Cobham» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.