P vs. NP

O maior mistério  da computação teórica tem até prêmio em dinheiro para quem resolver 💰👀

Já ouviu falar de

www.ciencia.ufpr.br

"se um problema é fácil de CONFERIR, será que ele também é fácil de RESOLVER?"

Em linhas gerais, a pergunta por trás do enigma é:

(validar, ver  se está certo)

(buscar e achar uma solução)

Resolver problemas e conferir resultados são as duas coisas que computadores fazem de melhor

A computação tem essa dúvida porque

O P vs. NP é considerado o maior mistério sem resposta da ciência da computação teórica e sua solução teria impacto profundo em diversas áreas da sociedade, da tecnologia e da ciência

E POR QUE ISSO É IMPORTANTE?

como? PRESTE ATENÇÃO

O que é o "P"?

O grupo P são os problemas que o computador resolve rapidamente

São tarefas eficientes, ou seja, o computador consegue resolvê-las logo mesmo que sejam muitos dados

Para entender a fórmula:

Exemplos: Achar o caminho mais curto no GPS ou organizar uma lista de nomes

E O que é o "NP"?

São problemas que às vezes parecem muito difíceis de resolver, mas são fáceis de conferir

Ou seja, só de bater os olhos você consegue saber se está resolvido

Exemplo: Resolver um Sudoku pode ser difícil, mas conferir se a resposta está certa é rápido

Se um problema é fácil  de conferir (NP), será que existe uma forma secreta  e super-rápida de resolvê-lo (P) que a humanidade ainda não descobriu?

O XIS DA QUESTÃO

Se P = NP, o mundo muda para sempre

e se a resposta fosse sim?

Significaria que toda a criptografia da internet poderia ser quebrada 🔓

Mas também que os computadores seriam capazes de descobrir a cura de doenças e prever o tempo com perfeição 🥹

A maioria dos cientistas aposta que P ≠ NP

e se a resposta FOR NÃO?

Isto é, há problemas que são e sempre serão difíceis demais para computadores resolverem em tempo útil 🤦🏽

Mas pelo menos dá para pensar em segurança na internet 🔒

TÁ, E O PRÊMIO? 💰

O enigma P vs. NP foi classificado como um dos  sete problemas do milênio pelo Instituto Clay de Matemática (CMI), de incentivo à área

O CMI oferece um prêmio de 1 milhão de dólares para a primeira solução correta

O prêmio é para solução correta, então... 

Fonte: uditangshu.com

Evite manipulações algébricas, estamos falando de conceitos 😉

Texto e edição Camille Bropp Texto e revisão Prof. Dr. André Vignatti Imagens wirestock/Magnific;  Niklas Konig/Unsplash; Giphy; CMI/Reprodução; uditangshu.com

(SDC/Sucom/UFPR)

(EXATAS/INFORMÁTICA/UFPR)