O Problema P Versus NP
1. Introdução
A Matemática não é uma ciência pronta e acabada conforme muitas pessoas poderiam pensar, pelo contrario existe uma quantidade significativa de trabalhos sendo produzidos que exploram tanto conhecimentos antigos aplicados para novos problemas como novos conhecimentos matemáticos aplicados para antigos problemas.
Clay Mathematics Institute é uma instituição privada estabelecida por um bem sucedido homem de negocio e sua esposa em 1998, nos EUA com a missão de “Desenvolver e disseminar o conhecimento matemático”, e para comemorar o inicio de um novo milênio o Clay Institute criou um concurso chamado “Millennium Problems” que é composto por sete problemas matemáticos, que são listados a seguir :
1. Conjectura de Birch e Swinnerton-Dyer
2. Conjectura Hodge
3. Equações de Navier-Strokes
4. P vs NP
5. Conjectura de Poincaré
6. Hipótese Riemann
7. Teoria de Yang-Mills
Cada um destes 7 problemas tratam de temas de grande relevância para a matemática moderna todos eles já eram conhecidos a anos, mais ninguém tinha sido capaz de prova-los.
Como incentivo o Clay Institute oferece um prêmio de um milhão de dólares para cada problema resolvido.
Uma curiosidade desta lista de sete problemas é complexidade envolvida até mesmo para entender a questão, na verdade acredito que mesmo um professor de matemática experiente pode ter grande dificuldade para entender todos eles.
Com base nesses dados autor desta obra teve iniciativa de escolher o problema que trata P vs NP como tema , este problema tem um aspecto prático para o homem moderno e uma possível solução pode ter conseqüência no dia-a-dia homem moderno.
Por isso esse texto tenta de maneira simples e não formalista enunciar a questão P vs NP, numa tentativa de tornar claro a todos do que se trata o problema e suas implicações.
Um aspecto interessante do problema P versus NP, é que ele esta relacionado não só a matemática, mas também a computação.
2. P versus NP
Complexidade computacional é um ramo da ciência da computação que visa classificar problemas computacionais de acordo com o nivel de dificuldade do problema.
A complexidade é medida conforme, independentemente do algoritmo, qual é quantidade necessarias de recursos, mas especificamente de tempo que é necessário para executar um algoritmo.
Para se realizar esta medida são coletados dados de uma execução básica, com menor entrada de dados possível, do algoritmo que resolve dado problema, com base neste tempo analiza se este tempo cresce de forma exponencial ou polinômial, caso o tempo cresça de forma polinomial a solução é considerada rápida de outra forma ela é considerada lenta.
É necessário notar que mesmo um algoritmo que cresce em tempo exponencial e portanto é considerado rápido, com uma entrada significativa pode levar um tempo realmente grande para ser executado, então, portanto entenda que o rápido citado pode não significar o rápido do senso comum.
Digamos que em um computador a soma de dois algarismos, 7 + 3, seja realizado com apenas duas operação básica do processador do computador, então:
A soma acima precisa de 2n operações(não é exatamente 2n operações, valor utilizado apenas para uma simplificação), onde n é número de algarismos das parcelas, para ser realizada computacionalmente, o que significa dizer que o tempo gasto para processar uma operação de adição computacionalmente tem um crescimento representado por uma função polinomial, normalmente é expresso por O(n) passos.
Outro exemplo de um algoritmo que é executado em tempo polinomial é o algoritmo da multiplicação requer operações , ou seja, a complexidade é de O(
) passos.
Com as informações acima podemos definir : Um algoritmo de tempo polinomial é um algoritmo que resolve o problema para todas as entradas possíveis em um tempo polinomial, os algoritmos de soma e multiplicação são exemplos destes tipos de algoritmos.
A partir disso dizemos que: a classe P de problemas é o conjunto de todos os problemas polinomiais [PF].
Podemos definir também de maneira informal, o que é um problema chamado razoável(feasible problem) : um problema é dito razoável [PF] :
Se for possível em tempo polinomial verificar se uma suposta solução é realmente uma solução para o problema. [PF]
Como exemplo somar dois números é um problema razoável, pois dado dois números e o soma deles é fácil verificar se a soma esta realmente correta, na verdade essa verificação também pode ser feita em tempo polinomial.
Vamos chamar este conjunto de problemas de NP(Non nondeterministic polynomial), é evidente que na verdade a classe P esta inserida dentro de NP, pois todo problema que pode ser resolvido em tempo polinomial pode também ser verificado em um tempo polinomial.
Então a questão P = NP poderia ser lida assim:
É verdade que todo problema cujas repostas podem ser checadas em tempo polinomial também podem ser resolvidos em tempo polinomial?
Quem conseguir resolver a questão P = NP, na verdade estará respondendo a esta pergunta. Dito assim o problema parece mais fácil do que realmente é, e também não parece ter uma implicação prática.
Um exemplo da relevância do problema é na criptografia, pois os principais algoritmos de criptografias atuais que são utilizados nas transações seguras da internet(SSL), baseiam-se na decomposição em fatores primos de números absurdamente grandes, números com mais 200 algarismos, pois atualmente não se tem conhecimento de um algoritmo que possa decompor em fatores primos números tão grande em um tempo razoável, ou seja, o algoritmo que soluciona o problema de decomposição em fatores tem um custo exponencial.
Uma conseqüência da prova de que realmente P = NP, seria que todos os algoritmos de criptografia baseado na decomposição em fatores primos estariam realmente em perigo.
Uma outra conseqüência de uma possível demonstração afirmativa P = NP teria repercusão na própria matemática e lógica, pois afirmaria que é computacionalmente possível a construção de um algoritmo capaz de provar qualquer teorema matemático.
A questão P = NP , já foi tratada pelos melhores matemáticos do mundo por varias décadas, e parece que nada de definitivo foi realmente provado sobre o tema, mas William I. Gasarch conduziu uma pesquisa com os melhores cientistas da computação e matemáticos do mundo sobre o tema, a maioria acha que na verdade P é diferente NP.
3. Referência
[PF]. Paulo Feofiloff http://www.ime.usp.br/~pf/
1. http://www.claymath.org
2. http://www.claymath.org/millennium/P_vs_NP/
3. STEPHEN COOK, http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf
4. http://www.cs.umd.edu/~gasarch/papers/poll.pdf


