http://www.guj.com.br/posts/list/2.java JForum - http://www.jforum.net
O professor [url=http://www.abc.org.br/org/aca.asp?codigo=sostenes]Sóstenes Lins[/url], da [url=http://www.ufpe.br]Universidade Federal de Pernambuco[/url], anunciou há alguns dias em seminário organizado pelo [url=http://www.dmat.ufpe.br/main/main.html]departamento de matemática[/url] 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.

[url=http://www.win.tue.nl/~gwoegi/P-versus-NP.htm]Existem algumas tentativas de prova[/url] e alguns pesquisadores adotaram uma abordagem diferente dizendo que o problema P=NP é indecidível, levando a questão aos trabalhos originais de [url=http://pt.wikipedia.org/wiki/Kurt_G%C3%B6del]Kurt Gödel[/url].

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

T+ ]]> http://www.guj.com.br/posts/preList/87430/467716.java http://www.guj.com.br/posts/preList/87430/467716.java GMT 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, [b]por aventura[/b], após ler o tópico inicial e ainda ficar [b]na dúvida[/b] sobre o que é essa "coisa" e suas implicações no nosso [b]dia-a-dia[/b], segue um texto, digamos, um pouco mais didático:
[b]P:[/b]
[quote]
... Algoritmos estão, na verdade, por trás de quase tudo o que acontece no mundo. O motor flex depende de algoritmos para analisar o resultado da compbustão e sintonizar o motor para a mistura de combustível que está no tanque. Seu banco -on e off line- é uma montanha de algoritmos. Assim como o sistema de saúde, o imposto de renda, a tv digital... o voar dos aviões, o sistema de controle de tráfego aéreo e por aí vai. Não, os pássaros ainda não são informatizados e seu voar é livre. por enquanto.

Pois bem. Os problemas computacionais do tipo P são aqueles em que o tempo [ou o custo] para tratar uma instância qualquer do problema é, no máximo, de ordem polinomial. Algo como o tamanho do problema elevado ao quadrado, por exemplo. Ou o tamanho do problema multiplicado pelo logaritmo dele mesmo, que vem a ser a complexidade de ordenar um arquivo qualquer [ou de começar com uma lista desordenada de palavras e deixá-la, ao fim do algoritmo, ordenada].

Há problemas cuja complexidade de solução depende de uma função não polinomial do tamanho da entrada, como seu fatorial [n! = 1* 2 * 3 * ... * n]. Gerar todas as permutações de um conjunto de N números gasta tempo N!, onde exclamação, aí atrás, é o símbolo para fatorial. Que vem a ser uma função que cresce muito depressa? Quer ver? Se um problema tem complexidade fatorial e seu tamanho é 3 [três objetos como entrada...], o custo de resolvê-lo é 6 [pois 1 * 2 * 3 = 6]. Tamanho 4 custa 24, 5 custa 120, 6 custa 720, 7 já vai pra 5040... e, se o problema for de tamanho 20, o custo é nada menos do que 2.432.902.008.176.640.000! Quase dois e meio quintilhões. Coisa de louco. Isso faz com que problemas para os quais não se conhece uma solução polinomial sejam, via de regra, considerados computacionalmente intratáveis.
[/quote]
[b]NP:[/b]
[quote]
...NP é a classe problemas considerados computacionalmente "razoáveis", aqueles para os quais, dada uma possível solução, pode-se testá-la em tempo polinomial. Ou seja, para os quais, se conseguirmos uma potencial solução de forma não determinística, temos um algoritmo lá da classe P que diz se a solução é verdeira ou não. Talvez venha, daí, o nome da classe: N de [b]"não determinístico"[/b] e [b]P de polinomial[/b]. Para mais detalhes sobre o assunto, de forma tão simples quanto é possível no caso, leia esta explicação do professor [url=http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/NPcompleto.html]Paulo Feofiloff[/url].

Juntando as duas coisas, chegamos ao título do texto de hoje: será que há uma solução polinomial para todos os problemas computacionalmente razoáveis? Será que, para cada e todo problema não determinístico polinomial [NP] eu consigo achar uma solução polinomial [em P]? ou seja, será que consigo provar que P=NP, que a classe dos problemas "razoáveis" tem complexidade polinomial, encerrando uma discussão iniciada em 1971 [[url=http://en.wikipedia.org/wiki/NP-complete#Background]por cook[/url]i] e ganhando um prêmio de [url=http://www.claymath.org/millennium/] [b]um milhão de dólares do clay institute[/b][/url]? E isso contra a opinião da vasta maioria dos cientistas da área? Em pesquisa recente, apenas 9 entre 100 cientistas que estão trabalhando no problema disseram acreditar que P=NP. e apenas 5 entre os 100 disseram que o problema seria resolvido -de uma forma ou de outra- antes de 2010.

Se P=NP, haverá conseqüências muito interessantes do ponto de vista de [entre muitas outras áreas] [b]logística, biologia, possivelmente criptografia e, talvez, toda a matemática[/b]. Porque provar teoremas se tornaria muito mais fácil, segundo o próprio Cook, o cientista que começou a discussão: [i]...it [P=NP] would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time... [/i] em suma, [b]parte da computação e matemática [/b] que está sendo feita e usada hoje [b]pode mudar consideravelmente[/b], com a provável inclusão, na lista, dos [b]sistemas de segurança das transações financeiras[/b]. Vai ser um auê federal. Mundial, aliás.
[/quote]
[b]Fonte completa[/b]: [url=http://silviomeira.blog.terra.com.br/p_np_sera]Blog Silvio Meira[/url] (Tomei a liberdade de fazer algumas correções de pontuação)
[b]Mais informações[/b]:
-[url=http://www.dm.ufscar.br/hp/hp501/hp501001/hp501001.html]P versus NP[/url]
-[url=http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/NPcompleto.html]Problemas polinomiais e NP-completos[/url]
-[url=http://www.furb.br/redemat/v3/rdm301/index.php3?iu_texto=18]SHOW DO MILHÃO[/url]

]]> http://www.guj.com.br/posts/preList/87430/467722.java http://www.guj.com.br/posts/preList/87430/467722.java GMT

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.]]> http://www.guj.com.br/posts/preList/87430/467754.java http://www.guj.com.br/posts/preList/87430/467754.java GMT
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?]]> http://www.guj.com.br/posts/preList/87430/467759.java http://www.guj.com.br/posts/preList/87430/467759.java GMT
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 ( ) , 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. ]]> http://www.guj.com.br/posts/preList/87430/467786.java http://www.guj.com.br/posts/preList/87430/467786.java GMT

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.]]> http://www.guj.com.br/posts/preList/87430/467806.java http://www.guj.com.br/posts/preList/87430/467806.java GMT 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.]]> http://www.guj.com.br/posts/preList/87430/467821.java http://www.guj.com.br/posts/preList/87430/467821.java GMT 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 ( ) , 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.]]> http://www.guj.com.br/posts/preList/87430/467824.java http://www.guj.com.br/posts/preList/87430/467824.java GMT 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?

[quote]
E se você tem a prova ( ) , 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.
[/quote]

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?]]> http://www.guj.com.br/posts/preList/87430/467855.java http://www.guj.com.br/posts/preList/87430/467855.java GMT
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 [i]Clay Mathematics Institute[/i]. 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.

[url]http://www.preprint.impa.br/[/url]]]> http://www.guj.com.br/posts/preList/87430/467902.java http://www.guj.com.br/posts/preList/87430/467902.java GMT
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 [i]Clay Mathematics Institute[/i]. 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.

[url]http://www.preprint.impa.br/[/url][/quote]

Beleza, obrigado. Valeu pela presteza. Era só curiosidade mesmo.]]> http://www.guj.com.br/posts/preList/87430/467939.java http://www.guj.com.br/posts/preList/87430/467939.java GMT
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 [i]Clay Mathematics Institute[/i]. 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.

[url]http://www.preprint.impa.br/[/url][/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. ]]> http://www.guj.com.br/posts/preList/87430/467949.java http://www.guj.com.br/posts/preList/87430/467949.java GMT Eu li algo assim em algum lugar que não me lembro aonde...
Enfim, TC rocks!]]> http://www.guj.com.br/posts/preList/87430/467966.java http://www.guj.com.br/posts/preList/87430/467966.java GMT 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.]]> http://www.guj.com.br/posts/preList/87430/467969.java http://www.guj.com.br/posts/preList/87430/467969.java GMT
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.

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+]]> http://www.guj.com.br/posts/preList/87430/468006.java http://www.guj.com.br/posts/preList/87430/468006.java GMT
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.

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.]]> http://www.guj.com.br/posts/preList/87430/468041.java http://www.guj.com.br/posts/preList/87430/468041.java GMT
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+]]> http://www.guj.com.br/posts/preList/87430/468126.java http://www.guj.com.br/posts/preList/87430/468126.java GMT 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.]]> http://www.guj.com.br/posts/preList/87430/468200.java http://www.guj.com.br/posts/preList/87430/468200.java GMT 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]

Ah, esse negócio de colorir grafos eu lembro: "Unfortunately a bug has been discovered in our algorithm"]]> http://www.guj.com.br/posts/preList/87430/468220.java http://www.guj.com.br/posts/preList/87430/468220.java GMT
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 ([url="http://www.flonnet.com/fl1917/19171290.htm"]indianos malucos[/url]) é primo em P seria um exemplo de NP que virou P?

]]> http://www.guj.com.br/posts/preList/87430/468256.java http://www.guj.com.br/posts/preList/87430/468256.java GMT
se vc procurar no google por P=NP e P<>NP vc vai ver, conclusões provando os dois lados ...
pura masturbação mental ...]]> http://www.guj.com.br/posts/preList/87430/468272.java http://www.guj.com.br/posts/preList/87430/468272.java GMT - Existem muitos problemas NP que depois concluiu-se que era P? Ou geralmente um NP fica sendo NP forever?
[/quote]

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

[quote=saoj]
A descoberta daquele algoritmo que prova se um número N ([url="http://www.flonnet.com/fl1917/19171290.htm"]indianos malucos[/url]) é primo em P seria um exemplo de NP que virou P?

[/quote]

Esse é o caso mais famoso.]]> http://www.guj.com.br/posts/preList/87430/468278.java http://www.guj.com.br/posts/preList/87430/468278.java GMT - Existem muitos problemas NP que depois concluiu-se que era P? Ou geralmente um NP fica sendo NP forever?

[/quote]

O problema são os NP-Completos]]> http://www.guj.com.br/posts/preList/87430/468289.java http://www.guj.com.br/posts/preList/87430/468289.java GMT - 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 (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.]]> http://www.guj.com.br/posts/preList/87430/468297.java http://www.guj.com.br/posts/preList/87430/468297.java GMT 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.
[/quote]

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? ]]> http://www.guj.com.br/posts/preList/87430/468306.java http://www.guj.com.br/posts/preList/87430/468306.java GMT - 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 (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.[/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]]> http://www.guj.com.br/posts/preList/87430/468310.java http://www.guj.com.br/posts/preList/87430/468310.java GMT [/quote]

Todos os NP-completos]]> http://www.guj.com.br/posts/preList/87430/468315.java http://www.guj.com.br/posts/preList/87430/468315.java GMT 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.]]> http://www.guj.com.br/posts/preList/87430/468317.java http://www.guj.com.br/posts/preList/87430/468317.java GMT
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! ]]> http://www.guj.com.br/posts/preList/87430/468323.java http://www.guj.com.br/posts/preList/87430/468323.java GMT 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+]]> http://www.guj.com.br/posts/preList/87430/468397.java http://www.guj.com.br/posts/preList/87430/468397.java GMT 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.]]> http://www.guj.com.br/posts/preList/87430/468430.java http://www.guj.com.br/posts/preList/87430/468430.java GMT MUITOs, mas MUITOS mesmo. Mas eram problemas que estavam em NP, e nao eram NP completos! Entao nao servem para "quebrar a banca", hehehe.
[/quote]
É 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.]]> http://www.guj.com.br/posts/preList/87430/468435.java http://www.guj.com.br/posts/preList/87430/468435.java GMT ... 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 [url=http://pt.wikipedia.org/wiki/Superfície_Costa]Superfície de Costa[/url]]]> http://www.guj.com.br/posts/preList/87430/468442.java http://www.guj.com.br/posts/preList/87430/468442.java GMT 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?
[/quote]

Aqui tem alguns:

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

T+]]> http://www.guj.com.br/posts/preList/87430/468698.java http://www.guj.com.br/posts/preList/87430/468698.java GMT 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.]]> http://www.guj.com.br/posts/preList/87430/468887.java http://www.guj.com.br/posts/preList/87430/468887.java GMT