Tese de Cobham

O grafo mostra o tempo da solução do problema em milissegundos (msec) vs. o tamanho do problema, n, para problemas de mochila resolvidos por um algoritmo especializado sofisticado utilizando um computador 933 MHz Pentium III (média de 100 instâncias, dados de:[1]). O encaixe da equação quadrática sugere que a complexidade algorítmica empírica para instâncias com 50–10,000 variáveis é O((log n)^2).

A Tese de Cobham, também conhecida como a tese de Cobham–Edmonds (assim denominada em referência a Alan Cobham e Jack Edmonds),[2][3][4] assegura que problemas computacionais podem ser resolvidos de maneira viável em algum dispositivo de computação apenas se forem computáveis em tempo polinomial, ou seja, se pertencerem à classe de complexidade P.[5]

Formalmente, para dizer que um problema pode ser resolvido em tempo polinomial significa dizer que existe um algoritmo que, dado uma instância de um problema de n bits como entrada, pode produzir uma solução em tempo O(n^c), onde c é uma constante que depende do problema mas não da instância particular do problema.

O artigo de 1965 de Alan Cobham intitulado "The intrinsic computational difficulty of functions"[6] (em português: A dificuldade computacional intrínseca das funções) é uma das menções mais antigas da classe de complexidade P, consistindo de problemas decidíveis em tempos polinomiais. Cobham teorizou que essa classe de complexidade era uma boa maneira de descrever o conjunto de problemas computáveis em tempo razoável. Qualquer problema que não pode estar em P não é razoável, mas se um problema do mundo real poder ser resolvido por um algoritmo existente em P, geralmente tal algoritmo será eventualmente descoberto.

A classe P é um objeto de estudo útil porque ela não é sensível aos detalhes do modelo de computação: por exemplo, uma mudança de uma máquina de Turing de uma única fita para uma máquina multifita pode trazer um aumento de velocidade quadrático, mas qualquer algoritmo que rode em tempo polinomial em um modelo também fará o mesmo no outro.

De modo similar, a classe de complexidade NC pode ser pensada como a classe de problemas "efetivamente solúveis" em um computador paralelo.

Referências

1. D. Pisinger, 2003. "Where are the hard knapsack problems? Arquivado em 23 de novembro de 2015, no Wayback Machine." (em inglês) Relatório Técnico de 2003/08, Departamento de Ciência da Computação da Universidade de Copenhaga
2. Oded Goldreich (2008), Computational complexity: a conceptual perspective, ISBN 978-0-521-88473-0 (em inglês), Cambridge University Press, p. 128 
3. Dexter Kozen (2006), Theory of computation, ISBN 978-1-84628-297-3 (em inglês), Birkhäuser, p. 4 
4. Egon Börger (1989), Computability, complexity, logic, ISBN 978-0-444-87406-1 (em inglês), Elsevier, p. 225 
5. Steven Homer e Alan L. Selman (1992), «Complexity Theory», in: Alan Kent e James G. Williams, Encyclopedia of Computer Science and Technology (em inglês), 26, CRC Press 
6. Alan Cobham (1965), «The intrinsic computational difficulty of functions», Proc. Logic, Methodology, and Philosophy of Science II (em inglês), Holanda do Norte