Você pode ter ouvido falar do famoso problema P versus NP. Se você puder provar ou refutar sua equação enigmaticamente curta, você seria um milhão de dólares mais rico, e talvez até bilhões de dólares, dependendo de seus escrúpulos.
A importância de P versus NP é principalmente em suas consequências para a computação. Acontece que é um dos sete problemas do Millennium Prize, o que significa que o Clay Mathematics Institute of Cambridge, Massachusetts, concederá US $ 1 milhão para quem tentar provar ou refutar a declaração. Mas se você provar que P, na verdade, é igual a NP, você nem precisaria do prêmio de $ 1 milhão. Como o cientista teórico Scott Aaronson explicou na semana passada em uma conferência em um auditório do Laboratório Nacional de Los Alamos, no Novo México, mostrando que P = NP abriria algumas possibilidades intrigantes.
“Se alguém provar que P = NP, a primeira coisa que eles devem fazer é roubar 200 bilhões de dólares em bitcoins. A segunda coisa que eles devem fazer é resolver o restante dos problemas do Millenium Prize “, disse Aaronson.
Para entender isso, você deve saber que os computadores são dispositivos que resolvem problemas, resumidos em um código legível pelo dispositivo de computação física, com base nos princípios descritos por Alan Turing. Resolver problemas toma várias etapas e um certo período de tempo, e o tempo necessário aumenta conforme o problema aumenta.
“P” refere-se aos problemas que os computadores resolvem o tempo todo, desde algo tão simples quanto a multiplicação de dois números até tarefas mais complexas, como navegar na Internet. Como um problema cresce em complexidade, a quantidade de tempo que leva para resolvê-lo cresce em “tempo polinomial”, onde um polinômio é um número com um poder e um coeficiente (como n2). Se um problema é solucionável em n2 vezes e duplica o tamanho da entrada, então a quantidade de tempo que levaria para resolvê-lo aumentaria em quatro.
No entanto, existem muitos problemas nos quais você pode determinar que uma resposta está correta em tempo polinomial, mas chegar a essa resposta pode ou não ser possível em tempo polinomial. Estes são chamados de “tempo polinomial não determinístico” ou problemas NP. O Sudoku é um problema do NP: difícil de resolver, fácil de verificar. Outro exemplo importante hoje é fatorar grandes números em números primos. Por enquanto, pelo menos, leva muito tempo, mais lento que o tempo polinomial, fatorar números muito grandes em números primos, mas verificar se uma resposta está correta é tão simples quanto multiplicar os números resultantes. Na verdade, essa ideia exata é a base da criptografia moderna, baseada na geração de chaves de segurança fáceis de verificar, mas difíceis de decifrar.
Os testes matemáticos mais recentes descobriram e podem continuar a encontrar soluções P para alguns desses problemas NP. O problema de P vs NP pergunta se cada problema de NP tem uma solução de P, ou se existe algum problema de NP que não pode ser resolvido em P. Parece que deveria ser óbvio que P não é igual a NP, mas não é rigorosamente e matematicamente testado. E se você provar que P é igual a NP, você também terá mostrado que existem algoritmos de tempo polinomial para um grande número de problemas de computador muito importantes. Você pode ficar muito rico: as chaves de mineração e segurança do bitcoin são baseadas em problemas NP difíceis de resolver e fáceis de verificar.
Computadores quânticos, que são baseados em matemática diferente de computadores clássicos, não prometem soluções P para todo problema NP. Uma vez pensou-se que eles poderiam resolver a classe mais difícil de problemas de NP, chamados problemas de NP. Se você pudesse encontrar uma solução eficiente para aqueles, você poderia encontrar soluções eficientes para todos os problemas NP. Isso inclui o problema do vendedor de rua e uma série de outros problemas de otimização semelhantes. Mas os computadores quânticos não corresponderam a esse exagero. Em contraste, computadores quânticos poderiam resolver alguns problemas de P em um tempo mais curto (como com um polinômio menor) ou mover alguns problemas de NP para a generalização quântica de P, chamada BQP ou “Erro polinomial quântico limitado por tempo”.
Então vá e tente provar novamente que P é igual ou diferente de NP. Se você tiver sucesso, você ganhará pelo menos um milhão de dólares, e talvez muito, muito mais.
Ou se preferir, quer aprender a lucrar e ter sucesso nesse mercado? Veja esse treinamento aqui.
Achou útil essa informação? Compartilhe com seus amigos! xD
Deixe-nos a sua opinião aqui nos comentários.
