Há
anos as maiores cabeças pensantes do mundo tentam descobrir se a equação P = NP
é verdadeira ou falsa. O Clay Mathematics Institute oferece 1 milhão de dólares
de recompensa para quem fizer uma prova formal que P = NP ou que P ≠ NP.
Para
começar, o que significa P e NP? Essas são duas categorias de problemas. A
categoria tipo P é quando existe um procedimento simples para encontrar a solução
de um problema, já a NP é um para
o qual é muito mais fácil checar se uma proposta de solução é correta do que
construir uma solução a partir do zero. Ou seja, Os problemas P possuem uma sequencia de passos para
se obter uma resposta rápida e direta do problema enquanto que os problemas NP
analisam cada uma das respostas possíveis, testando uma por uma, até encontrar
a solução certa.
Exemplos
de Problemas NP: Caixeiro Viajante, e o
problema da mochila; e os exemplos de Problemas P: Sistemas Lineares, equações,
e determinantes de matrizes.
Parece
simples? Eis a descrição do Instituto Clay: “Suponha que você esteja
organizando um evento para 400 pessoas numa universidade e que, nas instalações
universitárias, só haja acomodação para 100. Para complicar as coisas, o reitor
forneceu uma lista de pares de pessoas incompatíveis, que sempre brigam, e
exigiu que, na escolha final, nenhum desses pares aparecesse”. Aí está um
problema que mesmo os supercomputadores mais poderosos não conseguem resolver.
Se você tem em mãos uma lista de 100 possíveis convidados, conseguirá constatar
se ela satisfaz ou não às condições do reitor. Mas produzir tal lista do nada é
uma tarefa hercúlea. Na verdade, o número de possibilidades a testar é maior
que o número de átomos no universo. Esse é apenas um dos muitos problemas em
ciência da computação que apresentam a mesma característica. Dada uma resposta,
é possível verificar se ela é falsa ou verdadeira. Mas encontrar uma resposta a
partir do zero torna-se impraticável.
Se
o desafio P vs NP terminar provando que P = NP, os computadores poderão
resolver um monte de problemas complexos, passando por desdobramento de
proteínas e fatoramento de números enormes, o que tem várias implicações no
setor de criptografia aplicada aos
serviços militares e às transações comerciais e financeiras via Internet,
genética e até logística de distribuição de produtos, entre outros.

Nenhum comentário:
Postar um comentário