Sobre a questão do algoritmo para o problema do caixeiro viajante

Authors

Abstract

Sabemos já que há problemas para os quais se demonstrou que não existem algoritmos que os resolvam (como o problema da Paragem - Turing 1936, ou o 10º problema de Hilbert - Matijasevic, 1970), enquanto outros há que, apesar de ser possível construir algoritmos para a sua resolução, esses algoritmos possuem ordens de complexidade tão elevadas que originam a denominação de "ineficientes". O problema do Caixeiro Viajante encontra-se neste último caso, sendo classificado como NP-completo . Mas o que significa "NP-completo"? E será ou não possível encontrar um algoritmo "eficiente" para este problema? De facto, actualmente, não basta identificar um problema e garantir que existe pelo menos uma solução para ele, é ainda necessário saber se ele pode ser efectivamente resolvido em tempo e espaço de memória finitos e "realizáveis".

Keywords

NP-completeness

Subject

Complexidade computacional

Journal

Gazeta de Matemática, Vol. 138, pp. 29-39, Sociedade Portuguesa de Matemática, January 2000