P = NP

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

T+

JavaChild Membro desde: 30/03/2008 05:05:16 Mensagens: 125 Offline

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

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:

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

NP:

...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 "não determinístico" e P de polinomial. Para mais detalhes sobre o assunto, de forma tão simples quanto é possível no caso, leia esta explicação do professor Paulo Feofiloff.

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 [por cooki] e ganhando um prêmio de um milhão de dólares do clay institute? 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] logística, biologia, possivelmente criptografia e, talvez, toda a matemática. Porque provar teoremas se tornaria muito mais fácil, segundo o próprio Cook, o cientista que começou a discussão: ...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... em suma, parte da computação e matemática que está sendo feita e usada hoje pode mudar consideravelmente, com a provável inclusão, na lista, dos sistemas de segurança das transações financeiras. Vai ser um auê federal. Mundial, aliás.

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.

This message was edited 2 times. Last update was at 10/04/2008 08:13:53

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

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.

Paulo Silveira wrote: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.

This message was edited 1 time. Last update was at 10/04/2008 09:25:38

louds wrote:
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.

This message was edited 1 time. Last update was at 10/04/2008 09:29:00

thegoergen wrote:
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

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

louds wrote:
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?

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.

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?

This message was edited 1 time. Last update was at 10/04/2008 10:34:41

victorwss wrote:

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/

This message was edited 1 time. Last update was at 10/04/2008 10:45:09

thegoergen wrote:

victorwss wrote:

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

thegoergen wrote:

victorwss wrote:

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 wrote: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 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+