Buckminster
(usa Debian)
Enviado em 26/05/2017 - 23:31h
Bom, o problema do caixeiro viajante é um exemplo clássico de problema de otimização combinatória. A coisa básica, entre outras, a ser pensada nesse problema é reduzi-lo a um problema de enumeração. Acha-se todas as rotas possíveis e calcula-se o comprimento de cada uma delas para ver qual a menor rota.
Seguindo nessa estratégia reducionista, podemos calcular o comprimento total de cada rota e ver qual delas tem o menor comprimento total, o que seria uma tarefa fácil para um computador, porém, na prática não é o que acontece, pois o computador teria que ter uma memória ilimitada e irrestrita uma vez que aumentando-se o número de cidades o número do fatorial também aumenta.
Veja aqui:
http://www.mat.ufrgs.br/~portosil/caixeiro.html
No link acima vemos que o método reducionista não é prático (a não ser para o caso de poucas cidades). E costuma-se resumir essas propriedades do problema do caixeiro viajante dizendo que ele pertence à categoria dos problemas NP-completos.
A dificuldade de fatoração é de uma natureza diferente dos outros problemas de busca difíceis. Por exemplo, ninguém acredita que fatoração seja um NP-completo. Mas tem algumas exceções.
Veja:
http://www.inf.ufpr.br/vignatti/courses/ci165/23.pdf
Poderíamos partir do princípio que uma redução em tempo polinomial é uma redução que é computável por uma Máquina de Turing determinística em tempo polinomial onde a classe de complexidade P é o conjunto dos problemas de decisão que são solúveis em tempo polinomial.
E um problema pertence à classe NP se e somente se ele puder ser decidido em tempo polinomial por alguma Máquina de Turing não determinística. E um problema pertence à classe NP se ele puder ser verificado em tempo polinomial (por uma Máquina de Turing determinística).
Afirmando-se que todos os problemas de complexidade P são também de complexidade NP, mas o inverso "parece" não ser verdade, porém, não se pode afirmar isso com certeza, vemos que alguns problemas "parecem" não ter soluções passíveis de serem obtidas em tempo polinomial. E esse é todo o X da questão.
Entretanto, os algoritmos podem simplesmente ainda não serem conhecidos!
Veja:
http://sites.poli.usp.br/p/fabio.cozman/Didatico/Comp/Material/Turing.pdf
Um algoritmo é eficiente se ele é de complexidade polinomial no tamanho da entrada.
Vemos aqui
http://www.inf.ufg.br/~diane/PAA/2006/AULA2006/VerificacaoPolinomial.pdf que o grande questionamento é justamente esse: P = NP???
Não sei se ajudei ou compliquei mais ainda, procurei citar os links como uma base de partir para os estudos, mas o grande problema é justamente se P = NP, pois NP engloba P, mas P não engloba NP.
Caso fosse provado que P=NP, como o listeiro_037 disse, nasceriam novas classes de algoritmos, e essas classes seriam a Pedra Filosofal dos algoritmos computacionais.
Não gosto muito de citar a Wikipédia, mas no link abaixo tem uma explicação com propriedade do problema:
https://pt.wikipedia.org/wiki/P_versus_NP
E aqui:
http://paginas.fe.up.pt/~rossetti/rrwiki/lib/exe/fetch.php?media=teaching:1011:cal:16_1.16_2.npcompl...
Eu matutei um tempo em cima desse problema, isso em tempos antanhos, mas o problema é justamente que NP engloba P, mas P não engloba NP.
Minha sugestão é que você teria que criar outra linha de pensamento e a base disso, o começo seria estudar a Máquina de Turing a fundo.
