Por favor não me levem a mal, mas essa questão ainda me lembra aquela pergunta: “quem veio primeiro? o ovo ou a galinha?”
se vc procurar no google por P=NP e P<>NP vc vai ver, conclusões provando os dois lados …
pura masturbação mental …
MUITOs, mas MUITOS mesmo. Mas eram problemas que estavam em NP, e nao eram NP completos! Entao nao servem para “quebrar a banca”, hehehe.
Esse é o caso mais famoso.
O problema são os NP-Completos
Todos os problemas P são NP. A pergunta é se todos os NP são P também, ou então se existe algum NP que não é P.
Mais ou menos isso: Todos os cavalos § são animais (NP). A pergunta seria saber se existem animais que não são cavalos ou se todos os animais são cavalos.
Entendi. Por isso que eu preguntei se a maioria dos NPs viraram P ou continuam sendo NP.
Aquele dos primos demorou alguns séculos para virar P. Qual é o problema mais soda NP atual? Caixeiro viajante? 
[quote=victorwss][quote=saoj]
- Existem muitos problemas NP que depois concluiu-se que era P? Ou geralmente um NP fica sendo NP forever?
[/quote]
Todos os problemas P são NP. A pergunta é se todos os NP são P também, ou então se existe algum NP que não é P.
Mais ou menos isso: Todos os cavalos § são animais (NP). A pergunta seria saber se existem animais que não são cavalos ou se todos os animais são cavalos.[/quote]
Sim, mas tem alguns animais que eles ainda nao conseguiram mostrar que sao cavalos (mas tambem nao mostraram que nao sao). e acontece de um belo dia mostrarem que sao tambem cavalos, como o caso que ele citou, descartando aquele problema para uso da prova de que P!=NP
Todos os NP-completos
[quote=saoj]
Aquele dos primos demorou alguns séculos para virar P. Qual é o problema mais soda NP atual? Caixeiro viajante? :-)[/quote]
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.
Caros,
pra quem quiser saber mais sobre essa história de P == NP, segue um excelente link de um dos
maiores professores que eu conheço:
http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/NPcompleto.html
Nesse link possui uma versão “Não técnica” e uma versão “técnica”. Escolha o seu sabor e divirta-se! :lol:
[quote=Paulo Silveira][quote=Proteu Alcebidiano]
E quanto a ele ter anunciado que encontrou uma prova, acho que ele não está brincando em serviço. Ele anunciou uma prova construtivista para o problema, e ainda sendo uma complexidade alta (em torno de O(n^11)), a demonstração está contida em P. 
[/quote]
Ele nao eh o promeiro, assimm como quando “provaram” que colorir gravos era O(n a 6)… ai depois descobrem um acaso que fura o algoritmo.
Tenho professores que tambem trabalho com o assunto na USP, e eles tambem sao muito ceticos em relacao a essas noticia…
Ainda ha outra possibilidade de erro: de que a reducao do problemas que ele trabalhou para o 3-SAT esteja errada, e apenas o problema que ele trabalhou nao seja NP completo.[/quote]
É, o seminário que ele anunciou isso foi gravado em dvd, eu vou ver se consigo arrumar o vídeo publicado na web ou até mesmo publicar se alguém ainda não o fez.
E de fato, qualquer um deve ficar cético até ver o trabalho final dele, está em fase de finalização. Talvez o prazo de dois anos para refutar a afirmação seja insuficiente, dado o tempo que ele conhece e estuda o problema =)
T+
[quote=Paulo Silveira][quote=saoj]
Aquele dos primos demorou alguns séculos para virar P. Qual é o problema mais soda NP atual? Caixeiro viajante? :-)[/quote]
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.[/quote]
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.
É 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.
[quote=jmoreira]
… se dentro do prazo estabelecido ninguém no mundo conseguir desqualificar o trabalho deste professor, será um marketing fortíssimo para Brasil.[/quote]
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
Aqui tem alguns:
T+
[quote=dedejava][quote=Paulo Silveira][quote=saoj]
Aquele dos primos demorou alguns séculos para virar P. Qual é o problema mais soda NP atual? Caixeiro viajante? :-)[/quote]
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.[/quote]
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.[/quote]
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.