P = np

Assuntos Gerais
#1

O assunto não é propriamente notícia de Tecnologia (é Teoria da Computação) mas a afirmação P=NP tem impactos diretos no que fazemos, vou deixar aqui no off-topic mesmo, também para não desvirtuar um post por causa do comentário deste tópico, além de eu ter esquecido de postar esse assunto antes e não ter visto ele comentado até agora,

O professor Sóstenes Lins, da Universidade Federal de Pernambuco, anunciou há alguns dias em seminário organizado pelo departamento de matemática que conseguiu um resultado fabuloso no último semestre de 2007 no curso de otimização que ministrara, e que este problema implicaria em uma prova por contra-exemplo para uma das principais afirmações em aberto no campo da teoria da computação: se problemas NP-Completos são considerados problemas tratáteis (problemas polinomiais) ou intratáveis (complexidade pior do que polinomial).

Falando um pouco sobre o assunto, a pergunta P = NP basicamente nos diz que, se ela for verdadeira, significa que problemas considerados intratáveis podem ser enquadrados como tratáveis. Uma característica interessante do problema é que se for mostrado um contra-exemplo - isto é, se um problema declaradamente NP-Completo for resolvido com complexidade conputacional em P, todos os demais problemas NP-Completos também teriam uma maneira computacionalmente eficiente de serem resolvidos.

Outra implicação da afirmação P=NP é que isso seria uma demonstração com sucesso de se atacar correta e eficientemente um problema da classe NP-Completo.

Existem algumas tentativas de prova e alguns pesquisadores adotaram uma abordagem diferente dizendo que o problema P=NP é indecidível, levando a questão aos trabalhos originais de Kurt Gödel.

PS: Tive a infelicidade de comentar isso para colegas (inclusive aqui do GUJ) no dia primeiro de abril, que foi quando fiquei sabendo da notícia, já divulgada no meio acadêmico poucos dias antes. Difícil que areditaram desse jeito, não é?? hehe :XD:

T+

#2

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

#3

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.

#4

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?

#5

[quote=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?[/quote]

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:

#6

[quote=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.[/quote]

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

#7

[quote=louds]
O artigo em questão mostra que N éum subconjunto inteiramente contido em NP.[/quote]

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.

#8

[quote=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 [/quote]

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.

#9

[quote=Paulo Silveira][quote=louds]
O artigo em questão mostra que N éum subconjunto inteiramente contido em NP.[/quote]

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.[/quote]

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?

#10

[quote=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?[/quote]

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/

#11

[quote=thegoergen][quote=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?[/quote]

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/[/quote]

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

#12

[quote=victorwss][quote=thegoergen][quote=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?[/quote]

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/[/quote]

Beleza, obrigado. Valeu pela presteza. Era só curiosidade mesmo.[/quote]

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

#13

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!

#14

[quote=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![/quote]

Não.

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

#15

[quote=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?[/quote]

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

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+

#16

[quote=Proteu Alcebidiano][quote=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?[/quote]

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

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+[/quote]

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.

#17

[quote=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.[/quote]

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+

#18

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.

#19

[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. :wink:
[/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]

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

#20

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?