Tese de Cobham - Cobham's thesis

Não deve ser confundido com o teorema de Cobham .

A tese de Cobham , também conhecida como tese de Cobham – Edmonds (em homenagem a Alan Cobham e Jack Edmonds ), afirma que problemas computacionais podem ser computados de maneira viável em algum dispositivo computacional apenas se puderem ser computados em tempo polinomial ; isto é, se eles encontram-se na classe de complexidade P . Em termos modernos, identifica problemas tratáveis com a classe de complexidade P .

Formalmente, dizer que um problema pode ser resolvido em tempo polinomial é dizer que existe um algoritmo que, dada uma instância de n bits do problema como entrada, pode produzir uma solução em tempo O ( n c ), a letra O é notação big-o e C é uma constante que depende do problema mas não o caso particular do problema.

O artigo de Alan Cobham de 1965 intitulado "A dificuldade computacional intrínseca das funções" é uma das primeiras menções ao conceito da classe de complexidade P , que consiste em problemas decidíveis em tempo polinomial. Cobham teorizou que essa classe de complexidade era uma boa maneira de descrever o conjunto de problemas computáveis viáveis .

O artigo de 1965 de Jack Edmonds "Paths, trees and flowers" também é creditado por identificar P com problemas tratáveis.

Limitações

O gráfico mostra o tempo de solução do problema em milissegundos (mseg) vs. tamanho do problema, n, para problemas de mochila resolvidos por um algoritmo especializado de última geração usando um computador Pentium III de 933 MHz (média de 100 instâncias, dados de :). O ajuste 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 ) apesar de ter estimativa exponencial de complexidade de pior caso em teoria.

Embora a tese de Cobham seja um marco importante no desenvolvimento da teoria da complexidade computacional , ela tem limitações quando aplicada à viabilidade prática de algoritmos. A tese essencialmente afirma que " P " significa "fácil, rápido e prático", enquanto "não em P " significa "difícil, lento e impraticável". Mas isso nem sempre é verdade, porque a tese abstrai algumas variáveis ​​importantes que influenciam o tempo de execução na prática:

  • Ele ignora fatores constantes e termos de ordem inferior.
  • Ele ignora o tamanho do expoente. O teorema da hierarquia de tempo prova a existência de problemas em P requerendo expoentes arbitrariamente grandes.
  • Ele ignora o tamanho típico da entrada.

Todos os três estão relacionados e são reclamações gerais sobre a análise de algoritmos , mas se aplicam particularmente à tese de Cobham, uma vez que faz uma afirmação explícita sobre a praticidade. De acordo com a tese de Cobham, um problema para o qual o melhor algoritmo leva n 200 instruções é considerado viável, e um problema com um algoritmo que leva 2 0,00001 n instruções inviável - embora nunca se pudesse resolver uma instância de tamanho n = 2 com o algoritmo anterior , enquanto uma instância do último problema de tamanho n = 10 6 poderia ser resolvida sem dificuldade. Em campos onde os problemas práticos têm milhões de variáveis ​​(como Pesquisa Operacional ou Automação de Projeto Eletrônico ), até mesmo algoritmos O ( n 3 ) são freqüentemente impraticáveis.

Referências