latex

domingo, 8 de julho de 2012

P = NP ? valendo 1 milhão de dólares


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

Formulário de contato

Nome

E-mail *

Mensagem *

LinkWithin

Related Posts Plugin for WordPress, Blogger...

Anuncios