P = np

Me lembro ainda hoje de quando estudei os problemas P, NP e NP-C, na disciplina Complexidade de Algorithmos. Meu professor teve que se esforçar bastante para fazer a turma compreender esses problemas, matematicamente e computacionalmente.

Para aqueles que, por aventura, após ler o tópico inicial e ainda ficar na dúvida sobre o que é essa “coisa” e suas implicações no nosso dia-a-dia, segue um texto, digamos, um pouco mais didático:
P:

NP:

Fonte completa: Blog Silvio Meira (Tomei a liberdade de fazer algumas correções de pontuação)
Mais informações:
-P versus NP
-Problemas polinomiais e NP-completos
-SHOW DO MILHÃO

Sempre sai noticias de provas de P=NP… na USP ja tivemos uma palestra de uma professora que “provou”… mas isso deve acontecer 100x ao ano ao redor do mundo…

Se P=NP, toda a critatividade do mundo nao serve pra muita coisa, podemos usar um computador, que ele mesmo fara todas as descobertas da ciencia. P=NP teria um impacto muito maior do que os classicos “a criptografia atual estaria perdida”.

Acho que esse problema vai ficar no Clay institute por muito, muito tempo.

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?

victorwss:

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?

Acho que não adianta mostrar um exemplo de que P = NP, é preciso provar que TODOS os P são NP. A mesma coisa para o P != NP .

E se você tem a prova ( 8) ) , fale com algum professor do Departamento de Matemática de alguma Universidade, e fale com ele, explique a situação e ele pode te encaminhar para algum Congresso. Mas nunca libere a demonstração antes de ter a garantia de que ela nã será roubada.

Paulo Silveira:

Sempre sai noticias de provas de P=NP… na USP ja tivemos uma palestra de uma professora que “provou”… mas isso deve acontecer 100x ao ano ao redor do mundo…

Se P=NP, toda a critatividade do mundo nao serve pra muita coisa, podemos usar um computador, que ele mesmo fara todas as descobertas da ciencia. P=NP teria um impacto muito maior do que os classicos “a criptografia atual estaria perdida”.

Acho que esse problema vai ficar no Clay institute por muito, muito tempo.

O artigo em questão mostra que N éum subconjunto inteiramente contido em NP.

louds:

O artigo em questão mostra que N éum subconjunto inteiramente contido em NP.

Acho que voce quis dizer P em vez de N.

Mas P esta inteiramente contido em NP e isso eh trivial. nao entendi seu ponto.

editado: ja entendi, kumpera quis dizer que o artigo mostra que P eh subconjunto PROPRIO de NP. Ele traduziu as pressas. Ai sim faz sentido.

thegoergen:

Acho que não adianta mostrar um exemplo de que P = NP, é preciso provar que TODOS os P são NP. A mesma coisa para o P != NP .

E se você tem a prova ( 8) ) , fale com algum professor do Departamento de Matemática de alguma Universidade, e fale com ele, explique a situação e ele pode te encaminhar para algum Congresso. Mas nunca libere a demonstração antes de ter a garantia de que ela nã será roubada. :wink

Como assim pessoal??? TODOS os P sao NP e todo mundo sabe disso. Como falei no post anterior, isso eh trivial.

Acho que voces queriam falar o contrario. E mesmo assim ele tem razao, basta mostrar que UM problema NP-completo esta em P, que todos os outros vem junto, essa eh praticamente a definicao de problema NP-completo.

Paulo Silveira:

louds:

O artigo em questão mostra que N éum subconjunto inteiramente contido em NP.

Acho que voce quis dizer P em vez de N.

Mas P esta inteiramente contido em NP e isso eh trivial. nao entendi seu ponto.

editado: ja entendi, kumpera quis dizer que o artigo mostra que P eh subconjunto PROPRIO de NP. Ele traduziu as pressas. Ai sim faz sentido.

Ou seja, ele provou que são diferentes?

Ou seja, tenho que confiar em alguém que não conheço para ele fazer isso?
E como é que esse professor de algum departamento de matemática deveria proceder?

victorwss:

Ou seja, tenho que confiar em alguém que não conheço para ele fazer isso?
E como é que esse professor de algum departamento de matemática deveria proceder?

Bom… você não precisa confiar em alguém especificamente. Mas os doutores em Matemática estão mais acostumados com esse meio… E iria facilitar.

Existem intituos de matemática pelo mundo todo. O que dá o prêmio de 1 milhão é o Clay Mathematics Institute. Mas eu não sei como chegar até ele, por isso disse para procurar alguém de alguma Universidade.

Seria melhor ir direto ao IMPA ( Instituto de Matemática Pura e Aplicada ), que é no Brasil. Mais especificamente, no meio da Floresta da Tijuca, ao lado da Lagoa Rodrigo de Freitas, no Rio de Janeiro. Lá é o maior cérebro matemático do país, e onde estão os “caras”. Lá você precisa falar com alguém, que eu não sei quem…

[EDIT]

No site do IMPA você pode propôr uma publicação. Não sei como funciona, mas acho que você não precisa colocar a tua prova, só dizer que a demonstrou.

http://www.preprint.impa.br/

thegoergen:

victorwss:

Ou seja, tenho que confiar em alguém que não conheço para ele fazer isso?
E como é que esse professor de algum departamento de matemática deveria proceder?

Bom… você não precisa confiar em alguém especificamente. Mas os doutores em Matemática estão mais acostumados com esse meio… E iria facilitar.

Existem intituos de matemática pelo mundo todo. O que dá o prêmio de 1 milhão é o Clay Mathematics Institute. Mas eu não sei como chegar até ele, por isso disse para procurar alguém de alguma Universidade.

Seria melhor ir direto ao IMPA ( Instituto de Matemática Pura e Aplicada ), que é no Brasil. Mais especificamente, no meio da Floresta da Tijuca, ao lado da Lagoa Rodrigo de Freitas, no Rio de Janeiro. Lá é o maior cérebro matemático do país, e onde estão os “caras”. Lá você precisa falar com alguém, que eu não sei quem…

[EDIT]

No site do IMPA você pode propôr uma publicação. Não sei como funciona, mas acho que você não precisa colocar a tua prova, só dizer que a demonstrou.

http://www.preprint.impa.br/

Beleza, obrigado. Valeu pela presteza. Era só curiosidade mesmo.

victorwss:

thegoergen:

victorwss:

Ou seja, tenho que confiar em alguém que não conheço para ele fazer isso?
E como é que esse professor de algum departamento de matemática deveria proceder?

Bom… você não precisa confiar em alguém especificamente. Mas os doutores em Matemática estão mais acostumados com esse meio… E iria facilitar.

Existem intituos de matemática pelo mundo todo. O que dá o prêmio de 1 milhão é o Clay Mathematics Institute. Mas eu não sei como chegar até ele, por isso disse para procurar alguém de alguma Universidade.

Seria melhor ir direto ao IMPA ( Instituto de Matemática Pura e Aplicada ), que é no Brasil. Mais especificamente, no meio da Floresta da Tijuca, ao lado da Lagoa Rodrigo de Freitas, no Rio de Janeiro. Lá é o maior cérebro matemático do país, e onde estão os “caras”. Lá você precisa falar com alguém, que eu não sei quem…

[EDIT]

No site do IMPA você pode propôr uma publicação. Não sei como funciona, mas acho que você não precisa colocar a tua prova, só dizer que a demonstrou.

http://www.preprint.impa.br/

Beleza, obrigado. Valeu pela presteza. Era só curiosidade mesmo.

Foi nada. É que eu também já tive essa curiosidade. Mas como eu conmheço alguns doutores em Matemática, que inclusive vão às vezes para seminários e palestras no IMPA, é mais fácil. Se eu provasse algo, iria falar com eles que eles me encaminhariam… Eu não sabia ainda dessa de cadastrar no site, mas é uma boa.

Existe alguma coisa em Java que detecte o problema da parada?
Eu li algo assim em algum lugar que não me lembro aonde…
Enfim, TC rocks!

dedejava:

Existe alguma coisa em Java que detecte o problema da parada?
Eu li algo assim em algum lugar que não me lembro aonde…
Enfim, TC rocks!

Não.

Aliás, nem em java e nem em qualquer outra linguagem. Este problema é indecidível.

victorwss:

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+

Proteu Alcebidiano:

victorwss:

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:

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+

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:

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.

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”

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 …

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?

victorwss:

saoj:

• 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 § 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

Todos os NP-completos

saoj:

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.

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:

Paulo Silveira:

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.

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+

Paulo Silveira:

saoj:

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.

É 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:

… 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

Aqui tem alguns:

T+

dedejava:

Paulo Silveira:

saoj:

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.