P = NP

Proteu Alcebidiano wrote:

victorwss wrote:Enfim, ele anunciou que P=NP ou que P!=NP ?

Pois pode ser possível provar por contra-exemplos P=NP tanto quanto P!=NP.

E, tem algum link aí para algum artigo, ou qualquer coisa assim? Vi que ele descreveu que se tratava de um problema maluco de grafos, mas mesmo assim, eu queria pelo menos ler a suposta prova.

BTW, suponha que eu tenha uma prova de que P=NP ou que P!=NP e queira publicá-la. Como eu deveria proceder?

Ele anunciou que P=NP. Para P!= NP ou indecidível, nada muda nas nossas vidas, é como ele é conjecturado hoje.

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.

Quanto à ter que provar todos os problemas NP para resolver o problema, conforme mencionei, isso não é preciso, pois o problema por mais complicado que seja sem suas raízes na teoria de conjuntos. Se um dos elementos de um conjunto for demonstrado corretamente como fora dele, é porque os demais estarão também. Isso implica no conjunto fazer parte de outra definição, no caso, a de P.

T+

Supostas provas de que P=NP sempre me soam implausíveis porque isso implica que muita coisa tida como impossível é possível. A maioria dos especialistas aposta que P != NP ou que P vs NP é indecidível. Mesmo assim a quantidade de supostas provas que surge por aí tem uma tendência de P=NP significantemente maior.

E que o cara não brinca em serviço, disso eu não duvido. Porém muitos outros grandes gênios que também não brincavam em serviço elaboraram provas brilhantes (alguns de que P=NP e outros de que P!=NP). Porém, após uma análise aprofundada (que às vezes demora meses), alguém sempre encontrava um erro na prova.

Enfim, por isso é importante ver o artigo diretamente na sua fonte. Quanto mais gente avaliando, mais crédito pode ser dado a publicação, e mais cedo uma falha pode ser desmascarada. Embora por outro lado, publicar isso é trabalhoso: A prova tem que ser impecável para não ser invalidada por qualquer errinho idiota e é necessário vários cuidados para garantir-se de que ninguém a roube ou troque o nome do autor ou crie confusão quanto a sua autoria.

victorwss wrote:

Supostas provas de que P=NP sempre me soam implausíveis porque isso implica que muita coisa tida como impossível é possível. A maioria dos especialistas aposta que P != NP ou que P vs NP é indecidível. Mesmo assim a quantidade de supostas provas que surge por aí tem uma tendência de P=NP significantemente maior.

E que o cara não brinca em serviço, disso eu não duvido. Porém muitos outros grandes gênios que também não brincavam em serviço elaboraram provas brilhantes (alguns de que P=NP e outros de que P!=NP). Porém, após uma análise aprofundada (que às vezes demora meses), alguém sempre encontrava um erro na prova.

Enfim, por isso é importante ver o artigo diretamente na sua fonte. Quanto mais gente avaliando, mais crédito pode ser dado a publicação, e mais cedo uma falha pode ser desmascarada. Embora por outro lado, publicar isso é trabalhoso: A prova tem que ser impecável para não ser invalidada por qualquer errinho idiota e é necessário vários cuidados para garantir-se de que ninguém a roube ou troque o nome do autor ou crie confusão quanto a sua autoria.

Pois é, se tem normalmente um prazo de 2 anos para refutarem esse tipo de prova / desafio =)

Segundo o professor Sóstenes, ele está terminando os detalhes da sua prova. Agora é ver esperar..quem está acompanhando os detalhes acha que ele está certo, mas aí é submeter o trabalho para ficar acessível a quem também entende do assunto.

Considerando que o referido professor foi pioneiro nesse assunto no Brasil e em coisas correlacionadas, eu espero mesmo que ele tenha encontrado uma resposta definitiva para esta questão.

T+

Proteu Alcebidiano wrote:
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.

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.

Paulo Silveira wrote:

Proteu Alcebidiano wrote:
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.

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.

Ah, esse negócio de colorir grafos eu lembro: "Unfortunately a bug has been discovered in our algorithm"

This message was edited 1 time. Last update was at 10/04/2008 16:14:55

Manjo pouco disso, só sei que vale um milhão de dólares essa resposta, logo se alguém provou deve passar lá para pegar esse cascalho.

Para os matemáticos de plantão:

- Existem muitos problemas NP que depois concluiu-se que era P? Ou geralmente um NP fica sendo NP forever?

A descoberta daquele algoritmo que prova se um número N (indianos malucos) é primo em P seria um exemplo de NP que virou P?

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 ...

saoj wrote:
- Existem muitos problemas NP que depois concluiu-se que era P? Ou geralmente um NP fica sendo NP forever?

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

saoj wrote:
A descoberta daquele algoritmo que prova se um número N (indianos malucos) é primo em P seria um exemplo de NP que virou P?

Esse é o caso mais famoso.

saoj wrote:
- Existem muitos problemas NP que depois concluiu-se que era P? Ou geralmente um NP fica sendo NP forever?

O problema são os NP-Completos

saoj wrote:
- Existem muitos problemas NP que depois concluiu-se que era P? Ou geralmente um NP fica sendo NP forever?

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 (P) 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.

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.

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?

victorwss wrote:

saoj wrote:
- Existem muitos problemas NP que depois concluiu-se que era P? Ou geralmente um NP fica sendo NP forever?

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 (P) 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.

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

saoj wrote:Qual é o problema mais soda NP atual? Caixeiro viajante?

Todos os NP-completos

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.

Forum Spammer Membro desde: 30/07/2006 16:09:55 Mensagens: 1263 Offline

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!

Paulo Silveira wrote:

Proteu Alcebidiano wrote:
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.

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.

É, 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+

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