Resumo cap 15 livro o advento do algoritmo

CENTRO UNIVERSITÁRIO TIRADENTES – UNIT
ENGENHARIA MECATRÔNICA – NOITE
Alexandre Ferreira, Aramis Ocrécio, Elielton Antônio, Jorge Henrique, Sandro
José, Walter Palhares.

O capitulo 14 apresenta o problema bastante conhecido na área da computação, o caixeiro do viajante. Partindo de Witten, Iowa, o problema de Waterman era visitar Wittless, Grainball City, Sab Sac, Amblot e
Waterloo apenas uma vez e terminar a viagem em Wapping Falls.
O aspecto do problema é puramente teórico, Waterman precisa determinar quantas rotas possíveis pode levá-lo de cidade em cidade. Se há n cidades, há n! rotas possíveis entre elas, logo, há 5.040 rotas possíveis de sete cidades, mas se faz necessário saber quais sõa as rotas reais, as que estão ao seu dispor.
Escrever um algoritmo para resolver o problema é muito fácil. O programa pode dar uma solução satisfatória para o problema de Waterman logo na primeira vez que pegar o nome de uma cidade, mas a relação entre rotas e cidades é perigosamente instável. À medida que cidades são acrescentadas ao quadro de Waterman, o número de rotas entre elas cresce desmedidamente. Esse é um problema de interesse excepicional para os teóricos da informática. Um problema que pode ser resolvido em tempo polinomial pertence ao que é chamado de classe de complexidade P; e pertence a ela se sua solução pode ser encontrada em um número finito de passos. Na classe de complexidade NP, por outro lado, estão os problemas cujas as soluções podem ser verificados, mas não necessariamente encontradas em tempo polinomial. O problema de Waterman claramente pertence a classe
NP.
É a relação entre P e NP que é de grande interesse conceitual e prático. Claramente, P denota problemas tratáveis do mundo, e NP os problemas que não são tratáveis; e o que os teóricos e todo o resto do mundo gostariam de saber é se existe algum metódo para reduzir problemas intratáveis àqueles que são tratáveis.

O que Leonard Adelman fez para apresentar uma solução ao problema, foi