Será que P=NP ?
abr 17 por Bernardo
A mídia brasileira não ta nem aí. Mas a mídia científica internacional está com a respiração presa, esperando uma nova aparição do cientista Sóstenes Lins.
Pra se ter uma idéia do tamanho do evento que pode estar por vir, talvez o mundo esteja neste exato momento vivendo o começo de uma revolução tão grande quanto aquela provocada por Einstein (com a teoria da relatividade geral) e Descartes (com seu discurso do método).
Um brasileiro (nordestino pra ser exato) pesquisador lá de Recife (UFPE) afirma ter descoberto (e provado matematicamente) que há uma solução polinomial para todos os problemas computacionalmente razoáveis (o que é considerado hoje o maior problema não-resolvido da matemática).
Mas que diabos é isso? De forma bem resumida: Existem dois tipos de problemas: os triviais e os não triviais. Os problemas triviais são facilmente resolvidos, com operações matemáticas simples. Já os problemas não triviais só podem ser resolvidos com algoritmos. E é aí que mora o perigo.
Existem os problemas não-triviais tratáveis. Esses problemas tem algoritmos do tipo polinomial (lembra da quinta série?). Aí é “tranquilo”. Qualquer Pentium 100 consegue liquidar em segundos. Esses algoritmos são tidos como de “classe P”.
Alguns problemas não triviais não tem algoritmos de resolução conhecidos pelo homem. São chamados indecidíveis. Esses aí, a humanidade ainda vai levar alguns séculos pra resolver.
Mas existem problemas intratáveis. São esses o xis da questão. Eles tem algoritmos conhecidos, mas os algoritmos não são polinomiais. Por isto, alguns deles são tão complexos que nosso poder computacional atual não consegue resolvê-los. Esses algoritmos são tidos como de “classe NP”. São esses problemas que demandam super-computadores e que levam horas, dias, anos, séculos para serem resolvidos por uma máquina.
Por isso, os matemáticos estão sempre quebrando a cabeça pra transformar os algoritmos não-polinomiais em polinomiais. E eles tem tido sucesso em vários deles.
Até que um dia alguém perguntou: “peraí! Será que eu consigo transformar QUALQUER algoritmo não-polinomial e um algoritmo polinomial”? Em boa matemática: será que P=NP?
Se for, qualquer problema intratável passa a ser tratável.
E foi exatamente isso que o Sóstenes (disse que) fez.
E o que essa porcaria tem a ver com a sua vida? Tudo!
Você pode até não acreditar em mim. Mas as conseqüências deste teorema podem causar um terremoto e mudar (e muito) nossa vida. Para o bem e para o mal. Nada será como antes: matemática, criptografia, economia, logística, finanças, biologia, astronomia, previsões do tempo… (Veja algumas conseqüências aqui).
Só o Instituto Clay paga 1 milhão de dólares para o primeiro “Zé Mané” que provar que P=NP. Além disso, uma descoberta dessas, fatalmente resultará em um prêmio Nobel, que está na casa dos 2 milhões de dólares. Tudo isso é “trocado” (ou em bom “mineirês”: dinheiro de pinga) perto das implicações econômicas mundiais de tal descoberta.
Assim, esse tal Sóstenes Lins está há poucos meses de se tornar um milionário e o maior cientista brasileiro de todos os tempos (e um dos maiores do mundo). Ou (na hipótese dele ter errado nos cálculos) pagar o maior mico da história da ciência brasileira. Qual é a sua aposta?
mai 20 at 14:31
O Prof Sostenes Lins é muito capaz, e intelectualmente superior… Tudo é possível! Ele certamente tem o meu crédito, o problema é que esta redução não é trivial… Mas, quem sabe Sóstenes tem a carta!…
Recentemente um pessoal da Índia provou que definir se um número é primo está em P… Este problema era NP, ao que se sabia… Talvez uma janela tenha se aberto ai.
Boa sorte ao Sóstenes, estou torcendo por ele…
Marcos Negreiros
nov 05 at 20:54
olá
eu não estou por dentro das ideias do sostenes, mas estou curioso. eu tambem pesquisei uma resposta para o problema do caixeiro-viajante, só que pra mim p é diferente de np e vou colocar minha resposta para vocês analisarem, pois eu preciso saber a opinião concreta de outras pessoas.
Problema do caixeiro-viajante
Resposta de Will jadson de Jesus Cavalcante
Analisando todas possibilidades e vendo que todas as possíveis idéias se encaixavam no problema do caixeiro-viajante, que nele existem uma quantidade infinitas de sequencias dentro de um único problema, eu concluir que é um problema geral,total, infinitas sequencias dentro de uma sequencia, possui sequencias constante e sequencias inconstante. Outra conclusão é que se por exemplo você mudar apenas um valor entre a distancia de duas cidades nada mudarar nos valores das outras rotas, você pode até aumentar o valor de uma rota infinitamente e nada acontecerar com qualquer outra valor do mapa. Para se encontrar o caminho mais curto de um mapa quem que existir um padrão, uma ligação direta entre os elementos do problema. Este tipo de problema ele não tem mais informações que se poderia tirar do problema, as únicas informações estão nos próprios valores das distancias entre as cidades e se existisse teria que está bem nítido, não existe e eu nada que me impeça de mudar apenas um valor de distancia e nada acontecerar com os outros valores. Por exemplo, no números primos existe uma relação que os ligam, a idéia de que todos tem que ter como divisores o numero um e ele mesmo, logo existe uma ligação entre os primos. Outra conclusão,se escrevêssemos diferentes rotas em que a diferença de um para o outro é em apenas um elemento da sequencia e se esse número estiver no meio para o fim, uma maneira de encontrar o elemento de menor valor seria fazer cálculos com os primeiros elementos da sequencia, mas como a diferença de uma para a outra é de um único valor, os primeiros elementos da sequencia iriam servir para mais uma sequncia, logo não poderíamos diferenciar uma sequencia da outra, problemas que podem se ter sequencias desse tipo eu concluo que são imprevisíveis, inconstantes, logo eu digo que p é diferente de Np.
jun 08 at 18:04
Meu Deus. O pior que perdi meu tempo lendo isto. Premio Nobel e? Nobel de QUE? da Matematica? Existe? hehehehehe
Cara voce nao faz ideia do que ta falando.
“Por isto, alguns deles são tão complexos que nosso poder computacional atual não consegue resolvê-los” LOGICO QUE CONSEGUEM RESOLVER, SO QUE EM TEMPO NAO-POLINOMIAL (EXPONENCIAL).
Jesus, ainda falam que a inclusao digital faz bem …. tsc tsc
jun 12 at 19:10
Meu caro Arthur, você sabe do que está falando? Tome uma “maracujina” e aprenda um pouco.
O Prêmio Nobel foi uma brincadeira que, se você fosse mais espertinho, entenderia. É que existe, sim, um prêmio que todos no meio acadêmico chamam de Prêmio Nobel da Matemática, que seria o Prêmio Abel. Ele tem o mesmo impacto na vida do pesquisador e o mesmo valor financeiro. Pergunte para o seu professor de matemática (ou siga o link do “prêmio Nobel” que eu já coloquei para os mais lerdinhos).
Além disso, se você lesse meu texto direito, veria que eu nunca falei que os computadores não conseguem resolver problemas não-polinomiais. Eu só disse que com nosso PODER COMPUTACIONAL atual não conseguimos resolver ALGUNS deles. Isso porque o tempo seria muito grande – e isso torna o problema indissolúvel na prática. Sacou?
Lógico que é possível resolver computacionalmente qualquer problema com algoritmo conhecido. Qualquer aluno de primeiro ano de computação sabe disso. Mas se você pesquisar um pouco, vai perceber que não conseguimos resolver a maioria (e é por isso que a criptografia e outras coisinhas mais funcionam).
Além disso, peque um livrinho de algoritmos e aprenda que nem todo o algoritmo “não-POLINOMIAL” é EXPONENCIAL, como você pensa que é.
Entendeu? Ou quer que eu desenhe de novo?
ps: eu adoro a inclusão digital, mesmo com os leigos metidos a “entendidos” que aparecem por aí!