• Tecnologia E Inovação

O problema matemático que pode mudar o mundo: Será que P = NP?

Dependendo da resposta, um dos famosos problemas não resolvidos do Milênio pode ter grandes implicações em nossas vidas.

• Os Problemas do Prêmio do Milênio são um conjunto de sete problemas matemáticos não resolvidos apresentados pelo Clay Mathematical Institute, cada um com um prêmio de US $ 1 milhão para aqueles que os resolverem.
• Um desses problemas pergunta se P = Por exemplo . Simplificando, isso pergunta se os problemas computacionalmente difíceis realmente contêm soluções ocultas e computacionalmente fáceis. Isso, no entanto, é uma grande simplificação.
• Provando isso P não é igual Por exemplo seria um marco importante e é o resultado que a maioria dos cientistas da computação espera. No entanto, se o oposto for verdadeiro, então nosso mundo se tornaria drasticamente diferente do que é agora.

Em 2000, o Clay Mathematics Institute expôs sete problemas matemáticos não resolvidos e ofereceu US $ 1 milhão a quem pudesse resolvê-los. Até agora, apenas um dos sete chamados problemas do milênio foi resolvido: o Poincaré Conjecture , que tem a ver com como definir esferas em diferentes dimensões espaciais.

Para não matemáticos, tanto a natureza desse problema quanto por que ele valeria $ 1 milhão são um pouco difíceis de entender. No entanto, outro problema do milênio é um pouco mais fácil de entender e resolvê-lo teria consequências drásticas para o funcionamento do nosso mundo. Embora pareça mais simples, provar definitivamente esse problema de uma forma ou de outra iludiu os pesquisadores por décadas. A questão é se ou não P = Por exemplo .

O que são problemas P e NP?

Shutterstock

Simplificando, o P contra Por exemplo pergunta se o conjunto de problemas que podem ser facilmente resolvidos também está no conjunto de problemas que podem ser facilmente verificados. Imagine que você tenha a tarefa de colar uma xícara de chá quebrada de volta. É fácil ver se você conseguiu - você terá uma xícara de chá completa na sua frente. Mas é muito difícil pegar todas as peças díspares e encaixá-las novamente. Este é um exemplo de Por exemplo problema; difícil de resolver, fácil de verificar.

Agora imagine, em vez disso, que você tenha a tarefa de contar em quantos pedaços a xícara de chá se quebrou, em vez de remontá-la. Isso seria um P problema. É comparativamente mais fácil contar os pedaços quebrados do que descobrir como eles se conectam entre si.

Por que esses dois conjuntos de problemas são chamados de P e NP?

Algoritmos de computador demoram um certo tempo para resolver o problema de que foram encarregados. Geralmente, você pode estimar aproximadamente quanto tempo um algoritmo levará usando o número de elementos que eles precisam manipular. Cientistas da computação chamam o número de elementos N .

Como alguns algoritmos são mais ou menos eficientes do que outros, o tempo que levam para serem concluídos pode estar relacionado a N , N ^dois, N ³, e assim por diante. O importante, porém, é que o expoente é uma constante - é 1 ou 2, etc. Quando for esse o caso, diz-se que um algoritmo é concluído em tempo polinomial, ou P .

Infelizmente, nem todos os problemas funcionam dessa maneira. A resolução de alguns problemas pode levar um algoritmo a uma quantidade de tempo proporcional a 2 ^N , 3 ^N , e assim por diante. Nesse caso, N é o expoente, o que significa que cada elemento com o qual o algoritmo precisa lidar aumenta sua complexidade exponencialmente. Neste caso, o algoritmo pode ser concluído em tempo exponencial, ou Por exemplo (que realmente significa tempo polinomial não determinístico).

A diferença entre esses dois pode ser enorme. Se um P algoritmo tem 100 elementos, e seu tempo para concluir o trabalho é proporcional a N ³, então ele resolverá o problema em cerca de 3 horas. Se for um Por exemplo algoritmo, no entanto, e seu tempo de conclusão é proporcional a 2 ^N , então vai demorar mais ou menos 300 quintilhões de anos.

Por que isso importa?

Usuário do Flickr Jan Kaláb

Outra maneira de perguntar se P = Por exemplo é perguntar se todo problema difícil realmente contém uma solução fácil, mas oculta. Esses dois tipos de problemas estão irrevogavelmente separados um do outro? Alguns problemas são simplesmente complexos por sua natureza fundamental?

Se P faz igual Por exemplo , então teria algumas implicações importantes para o nosso modo de vida. Um grande benefício é que muitos Por exemplo problemas são referidos como sendo Por exemplo -completo, o que significa que suas soluções podem ser rapidamente adaptadas a qualquer outro Por exemplo -problema completo. Então, desenvolvendo uma maneira de resolver rapidamente um Por exemplo - um problema completo daria passos significativos para completar todos os outros Por exemplo -Problemas completos.

Quais são alguns exemplos de Por exemplo problemas? Muitos pesquisadores se concentram em uma grande preocupação. A maior parte da criptografia moderna depende de códigos que são difíceis de decifrar, mas fáceis de verificar. Por exemplo, considere as senhas ou PINs de suas várias contas. Verificar se eles estão corretos é simples, mas adivinhando de força bruta cada permutação de letras e números levaria para sempre . A criptografia por trás da proteção do número do seu cartão de crédito ao fazer um pedido na Amazon também é um exemplo de Por exemplo criptografia. Se P = Por exemplo , então quebrar quase todo tipo de criptografia se tornaria repentinamente muito, muito mais fácil.

Embora perder qualquer aparência de segurança na Internet fosse desastroso, haveria muitas consequências benéficas se P = Por exemplo . Lance Fortnow, cientista da computação e autor de O Bilhete Dourado: P, NP e a Busca pelo Impossível, resumiu algumas das principais consequências em um artigo para Comunicações do ACM :

O transporte de todas as formas será programado de maneira ideal para movimentar pessoas e mercadorias de maneira mais rápida e barata. Os fabricantes podem melhorar sua produção para aumentar a velocidade e criar menos resíduos. E estou apenas arranhando a superfície. O aprendizado se torna fácil usando o princípio da navalha de Occam - simplesmente encontramos o menor programa consistente com os dados. O reconhecimento da visão quase perfeita, a tradução e compreensão da linguagem e todas as outras tarefas de aprendizagem tornam-se triviais. Também teremos previsões muito melhores de clima, terremotos e outros fenômenos naturais.

Esta questão de se P = Por exemplo é tão fundamental que é difícil selecionar apenas um punhado de tarefas representativas que poderiam ser melhoradas em anos-luz. Seria relativamente fácil, por exemplo, prever estruturas de proteínas a partir de seus sequências de aminoácidos , um marco importante para o desenvolvimento de medicamentos e biotecnologia. Outro comumente citado Por exemplo o problema é como determinar mais layout eficiente de transistores em um chip de computador, aumentando significativamente o poder de computação.

Na verdade, provando P = Por exemplo tornaria muito, muito mais fácil resolver quase todos os outros problemas matemáticos. Fortnow também escreveu que 'uma pessoa que prova P = NP voltaria do Clay Institute para casa não com $ 1 milhão de cheque, mas com sete (na verdade, seis, já que a conjectura de Poincaré parece resolvida).

Em última análise, as consequências de provar que P = Por exemplo seria a reviravolta total das atuais bases tecnológicas e econômicas da sociedade. Muito provavelmente, resolver esse problema seria um impulso inovador semelhante, senão maior do que a invenção da Internet.

O consenso científico

Infelizmente, a maioria dos cientistas da computação não acredita que P = Por exemplo —A partir de 2012, 83% dos cientistas da computação não acreditava que essa proposição fosse verdadeira. É muito difícil provar uma negativa, mas todas as tentativas fracassadas de provar que P = Por exemplo Dê crédito à ideia de que os dois tipos de problemas são, em última análise, irreconciliáveis. Cientista do MIT Scott Aronson escreveu uma postagem no blog listando dez motivos pelos quais P provavelmente não é igual Por exemplo , e o número nove apresenta um argumento que dissipa significativamente a ideia de que P = Por exemplo e descreve sucintamente as consequências se fosse verdade:

Se P = NP, então o mundo seria um lugar profundamente diferente do que geralmente supomos que seja. Não haveria nenhum valor especial em 'saltos criativos', nenhuma lacuna fundamental entre resolver um problema e reconhecer a solução depois de encontrada. Todos que poderiam apreciar uma sinfonia seriam Mozart; todos que pudessem seguir um argumento passo a passo seriam Gauss; todos que pudessem reconhecer uma boa estratégia de investimento seriam Warren Buffett.

Qualquer pessoa pode ser uma pessoa da matemática - desde que compreenda isso.

Compartilhar: