01/07/2008

P=NP?



Este é um dos problemas ainda sem solução apresentados pelo Clay Mathematics Institute no inicio deste milénio. Na verdade dos sete problemas apresentados, apenas um, a Conjectura de Poincaré, foi resolvido.
Este é um problema matemático com implicações em computação e cuja resolução, caso se verifique a igualdade, trará alguns problemas.
Mas afinal o que significa P e NP? O que significa P=NP?
Traduzindo para miúdos, o que se quer saber é se um problema em que se consegue verificar uma possível solução facilmente também pode ser resolvido facilmente.
P representa os problemas cuja solução é fácil de encontrar e NP problemas cuja solução é fácil de verificar. Dentro dos problemas NP existem problemas do tipo NP-completos, um exemplo destes últimos é o exemplo do caixeiro-viajante. Um caixeiro viajante tem que percorrer "n" cidades e quer saber qual o melhor caminho de maneira a percorrer uma menor distancia entre todas as cidades.
Os problemas NP-completos têm uma particularidade, é que se alguém conseguir arranjar um algoritmo que resolva um problema esse algoritmo pode ser traduzido de maneira a resolver qualquer problema do tipo NP.
Se realmente se provar que P=NP, serão resolvidos alguns problemas informáticos e outros mais práticos que têm a ver com a industria, mas por outro lado também aparecerão outros problemas... O tipo de problemas que aparecerão têm a ver com transição de dados via net, como transacções financeiras, por exemplo. As transacções financeiras baseiam-se em mensagens encriptadas.
Mas existem boas noticias para todos aqueles que poderiam sair prejudicados: Os entendidos não acreditam que P seja igual a NP!
É muito mais fácil confirmar se um código corresponde à combinação certa de um cofre do que descobrir qual é a combinação certa deste. Portanto, há problemas em que se verifica facilmente as possíveis soluções mas que são muito difíceis de resolver.
Não muita razão para alarme =P

2 comentários:

antonio ganhão disse...

É por isso que eu digo: não existe alternativa ao Sócrates!... estou a brincar.

Metódica disse...

Normalmente se tem apenas uma opção... :P