Eu gostaria de saber sobre a história desses dois termos: " eficiente ", " viável ".
Quem os usou sobre computação / algoritmos pela primeira vez? (no sentido moderno desses termos, ou seja, século 20). Como eles se tornaram mainstream? Como esses dois termos começaram a ser usados como sinônimos?
Eu sei que Cobham usou o termo "viável" na declaração de sua tese que se associava à computabilidade polinomial do tempo. Mas existe uma referência anterior? Não parece haver uma referência explícita a esses termos na carta de Godel a von Neumann . Não pude encontrar nenhum artigo relacionado anterior a 1960 (usando o Google Scholar ).
Outro ponto interessante é que o título do artigo de Cobham de 1965 é "A dificuldade computacional intrínseca das funções". Quando a "complexidade computacional" substituiu a "dificuldade computacional"?
Outra frase a considerar é "exatamente solucionável", que é da física estatística e também corresponde às nossas noções atuais de eficiente / viável. A introdução neste artigo contém uma boa descrição histórica dessa frase com muitas referências.
fonte
Não foi exatamente o que você pediu, mas é muito longo para comentar.
A referência explícita mais antiga que conheço a um algoritmo inviável é no Memorando de Évariste Galois, sobre as condições de resolução de equações por rádio , escrito em 1830:
Embora seja verdade que o algoritmo de Galois não é executado no tempo polinomial, Galois claramente significava algo muito menos preciso. Essa também é a referência mais antiga que conheço que considera a mera existência de um algoritmo significativo por si só.
Como Niel de Beaudrap menciona nos comentários, Gauss já discutiu a (in) eficiência de algoritmos para testes de primalidade em suas 1801 Disquisitiones Arithmeticae , quase 30 anos antes de Galois. Para completar, eis a passagem relevante do artigo 329:
fonte
Editar: Resposta reescrita
Como ficou popular? provavelmente espalhando a idéia de comparar novas pesquisas com as mais antigas em termos de desempenho, com a suposição de que criar novas idéias é mais difícil.
fonte