Tese de Cobham
Em ciência da computação , a tese de Cobham , também conhecida como tese de Cobham-Edmonds (em homenagem a Alan Cobham e Jack Edmonds ), postula que problemas "facilmente" computáveis são problemas computáveis em tempo polinomial. Em particular, os problemas de decisão calculável "facilmente" são os da classe P .
(1965) artigo de Alan Cobham é chamado A dificuldade computacional intrínseca das funções e é uma das primeiras ocorrências da classe P .
Esta tese é importante porque a classe P é precisamente uma classe que não é sensível aos detalhes de um modelo computacional: por exemplo, uma máquina de Turing com uma banda ou com várias bandas dá a mesma definição da classe P.
Esta tese foi criticada por não levar em consideração o expoente do polinômio, mas de acordo com o teorema da hierarquia de tempo determinística , existem problemas onde o melhor algoritmo tem um expoente arbitrariamente grande.
Notas e referências
-
D. Pisinger, 2003. "Onde estão os problemas difíceis da mochila?" Relatório Técnico 2003/08, Departamento de Ciência da Computação, Universidade de Copenhague, Copenhague, Dinamarca, ver [1] , acessado em 31 de janeiro de 2015.
-
(in) Oded Goldreich , Complexidade computacional: uma perspectiva conceitual , Cambridge, Cambridge University Press ,
2008, 606 p. ( ISBN 978-0-521-88473-0 , leitura online ) , p. 128
-
(in) Dexter Kozen , Teoria da Computação , Londres, Birkhauser,
2006, 418 p. ( ISBN 978-1-84628-297-3 , leitura online ) , p. 4
-
(em) Egon Boerger ( trad. Do alemão), Computabilidade, complexidade, lógica , Amsterdã / Nova York / Nova York, NY, EUA, Elsevier ,
1989( ISBN 978-0-444-87406-1 , leitura online ) , p. 225.
-
Steven Homer e Alan L. Selman, "Complexity Theory", em Encyclopedia of Computer Science and Technology , vol. 26, CRC Press,
1992( leia online )
-
Alan Cobham , "A dificuldade computacional intrínseca das funções", em Proc. Lógica, Metodologia e Filosofia da Ciência II , North Holland,
1965