P = NP

This message was edited 1 time. Last update was at 11/04/2008 06:56:19

Paulo Silveira wrote:

saoj wrote:
Aquele dos primos demorou alguns séculos para virar P. Qual é o problema mais soda NP atual? Caixeiro viajante?

Caixeiro viajante ja eh diferente, pois é NP completo. Ai tanto faz qualquer problema NP completo, ja que um é tão complicado quanto o outro, e se resolverem um em tempo polinomial, todos os outros estao resolvidos... Entre os NP completo, nao existe isso de mais ou menos dificil.... sao equivalentes.

Mas o problema do TSP tem boas aproximacoes, que poderia ser um criterio para usar em relacao ao mais "dificil" entre lees.

Eu concordo com a sua última afirmação. Na verdade, eu pensava que o TSP era decidível e intratável (tem como achar resposta para um determinado número de cidades, acho que são 19, mas com 20 a explosão combinatória é tão grande que ele se torna intratável). Ele sendo decidível tem como ser NP completo?
Conheço poucos probelmas NPs. O problema da parada, ver se uma gramática é ambígua e achar um número perfeito que seja ímpar. Alguém conhece mais?

Abraço.

JavaChild Membro desde: 30/03/2008 05:05:16 Mensagens: 125 Offline

Paulo Silveira wrote:
MUITOs, mas MUITOS mesmo. Mas eram problemas que estavam em NP, e nao eram NP completos! Entao nao servem para "quebrar a banca", hehehe.

É possível que este professor NAO esteja "blefando", mas, considerando a amplitude do problema, seu trabalho será fortemente explorado mundo a fora. Assim, considerando que muitos NP na verdade era P, como citado, então, o foco dos que tentarão desqualificar o trabalho será provar que o problema que ele escolheu para resolver na verdade é um NP e NAO um NP-C e que, possívelmente é um P... Em fim...
Como o professor AINDA irá publicar o paper, não adianta especular muito. É esperar para ver. Mas, como citado, se dentro do prazo estabelecido ninguém no mundo conseguir desqualificar o trabalho deste professor, será um marketing fortíssimo para Brasil.

jmoreira wrote:
... se dentro do prazo estabelecido ninguém no mundo conseguir desqualificar o trabalho deste professor, será um marketing fortíssimo para Brasil.

Exatamente. E se realmente isso se confirmar, o Brasil talvez não seja mais lembrado apenas como o país do Futebol, Praia e Carnaval.
Acredito que matemáticos famosos o país nunca teve, excetuando talvez o cara que descobriu a Superfície de Costa

dedejava wrote:
Conheço poucos probelmas NPs. O problema da parada, ver se uma gramática é ambígua e achar um número perfeito que seja ímpar. Alguém conhece mais?

Aqui tem alguns:

http://en.wikipedia.org/wiki/List_of_NP-complete_problems

T+

dedejava wrote:

Paulo Silveira wrote:

saoj wrote:
Aquele dos primos demorou alguns séculos para virar P. Qual é o problema mais soda NP atual? Caixeiro viajante?

Caixeiro viajante ja eh diferente, pois é NP completo. Ai tanto faz qualquer problema NP completo, ja que um é tão complicado quanto o outro, e se resolverem um em tempo polinomial, todos os outros estao resolvidos... Entre os NP completo, nao existe isso de mais ou menos dificil.... sao equivalentes.

Mas o problema do TSP tem boas aproximacoes, que poderia ser um criterio para usar em relacao ao mais "dificil" entre lees.

Eu concordo com a sua última afirmação. Na verdade, eu pensava que o TSP era decidível e intratável (tem como achar resposta para um determinado número de cidades, acho que são 19, mas com 20 a explosão combinatória é tão grande que ele se torna intratável). Ele sendo decidível tem como ser NP completo?
Conheço poucos probelmas NPs. O problema da parada, ver se uma gramática é ambígua e achar um número perfeito que seja ímpar. Alguém conhece mais?

Abraço.

Cara, você está confundindo as coisas. O problema da parada e o da gramática ambígua são recursivamente-enumeráveis-completos, e não NP-completos.
O do número perfeito ímpar não sei se é RE-completo, mas com certeza não é NP-completo.

Os problemas recursivamente enumeráveis completos necessitam de tempo infinito para se encontrar a solução definitiva.

Os problemas de NP sempre podem ser solucionados em tempo finito, e portanto NP e RE-completo são classes totalmente distintas.

O negócio do NP-completo é que todos os algoritmos conhecidos precisam de tempo exponencial para tratar o pior caso do problema (exponencial é muito grande, mas nunca é infinito).

Não confunda alhos com bugalhos.

Notícias, artigos e o maior fórum brasileiro sobre Java