 | |
| Homer Simpson contemplando o abismo |
Muito se fala de um dos sete problemas do Prêmio do Millenium, que, se solucionado teria um impacto sem precedentes na computação e nos mais diversos campos da ciência. O que de fato é "P vs. NP"?
Para compreendermos do que se trata precisamos antes responder às seguintes perguntas: “O que é algoritmo?” e “O que é complexidade de algoritmo?”.
No nosso dia-a-dia nos defrontamos com situações em que, dado um objetivo inicial, se faz necessário que sigamos um passo-a-passo para que atingi-lo. Por exemplo: para fazer um bolo, dados os ingredientes necessários, seguimos à risca uma receita e só então temos um bolo.
Na área de computação chamamos essas “receitas” de algoritmos, dada uma situação problema fazemos uso deles para chegar a uma solução. Existem infinitas maneira de solucionar um problema e a maneira que temos de avaliar o quão melhor é uma solução em relação à outra é através da complexidade de algoritmos, que quantifica o número de "passos" executados para se resolver o problema, basicamente o tempo de execução, e o quanto da memória do computador é usada nesse processo.
Agora façamos o seguinte exercício mental: dada uma lista não ordenada de número, determine qual é o maior.
A = { 5, 11, 6, 1, 20, 31, 17}
O algoritmo para se determinar o maior número é algo como:
Candidato a maior número é 0.
5 é maior que 0? Sim.
Candidato a maior número é 5.
11 é maior que 5? Sim.
Candidato a maior número é 11.
…
E assim sucessivamente até não sobrar mais números para comparar e chegarmos à conclusão de que o maior número é 31, a quantidade de comparações ou passos que devemos realizar até chegar ao resultado é proporcional à quantidade de números pertencentes à A. Quanto maior A, maior a quantidade de comparações, e maior tempo de execução do algoritmo, que cresce de forma linear. Temos então um problema com algoritmo de complexidade N.
Entretanto, a grande maioria dos problemas (e suas respectivas soluções) tem complexidade muito maior do que isso. Há problemas cuja melhor solução encontrada é de complexidade proporcional à N² ou N³, ou N vezes o logaritmo de N… Chamamos esses problemas de Problemas-P ou Polinomiais. Em contrapartida, há aqueles problemas ainda mais difíceis de resolver, cuja melhor solução conhecida é de complexidade 2^N ou ainda N! a que chamamos de Problemas-NP ou Não Polinomiais.
Um algoritmo que leva um tempo proporcional a N³ é mais lento do que um de complexidade N mas essa diferença se torna ainda maior quando falamos de Problemas-NP, quando N assume valores suficientemente grandes o tempo de execução do algoritmo torna-se impraticável.
 |
| Tempo de execução de algoritmos de diferentes complexidades em função do tamanho da entrada |
A razão para P vs. NP atrair tanta atenção, além do prêmio de um milhão de dólares, são as consequências práticas. Se fosse provado que P = NP, o que possivelmente traria consigo algoritmos muito mais eficientes do aqueles que existem hoje em dia. Haveriam grandes avanços nos mais diversos campos da ciência. Como exemplo temos o problema do Caixeiro Viajante, com diversas aplicações em logística e biologia, mas cuja solução num modelo exato é de complexidade N!.
 |
| Grafo numa representação do problema do caixeiro viajante |
E você, acha que P = NP ou não? ;)
Fontes:
Este comentário foi removido pelo autor.
ResponderExcluirSegundo um artigo publicado por Norbert Blum,que diz ter resolvido este problema, P NÃO e igual a NP. Apesar de muitos matemáticos concordarem, outros ainda não sabem ao certo, pois isso não é um fato muito bom a se aceitar.
ResponderExcluir