Quem resolver este problema matemático pode roubar todas as bitcoins do mundo

Existem alguns problemas matemáticos cujas soluções valem, literalmente, um milhão de dólares. O problema do “P versus NP” é um deles. Quem o resolver pode roubar todas as bitcoins do mundo.

Ligado à ciência da computação, um problema P é um problema cuja resposta é fácil de encontrar. Um NP é um problema cuja resposta é fácil de verificar. A grande questão é se existe ou não um problema que é fácil para um computador verificar, mas incrivelmente difícil para ele resolver.

A solução do problema “P versus NP” pode render um prémio do instituto norte-americano Clay Mathematics Institute. Este é um dos “Problemas do Prémio Millennium” — sete problemas matemáticos altamente complicados e para os quais ainda não foi encontrada solução.

Ascánder / Wikimedia

P=NP, o (até agora) indecifrável problema matemático

Ou seja, se conseguir solucionar este problema, pode rapidamente tornar-se milionário. O curioso é que nem precisa de prémio nenhum, porque se realmente puder provar que P é igual a NP, a solução para essa equação traz possibilidade emocionantes.

“Se alguém provar que P = NP, a primeira coisa que deve fazer é roubar 200 milhões de dólares em bitcoins. A segunda que deve fazer é resolver todos os outros problemas do Prémio Millennium”, explicou o cientista computacional Scott Aaronson.

Para um computador, resolver problemas significa cumprir uma série de passos e levar um determinado tempo para fazê-lo.

Computadores clássicos resolvem constantemente problemas P, como multiplicar dois números ou navegar na Internet. Quanto mais complexo é esse problema, mais tempo o computador leva para solucioná-lo. O aumento é representado por aquilo que chamamos de “tempo polinomial”, em que um polinómio é um número com uma potência e um coeficiente (como n²). Se um problema é solucionável em n² e torna-se duas vezes mais difícil, então a quantidade de tempo para resolvê-lo aumenta quatro vezes.

É aqui que as coisas complicam um pouco: existem problemas cuja solução pode ou não ser resolvida em tempo polinomial, mas essa mesma solução pode com certeza ser verificada (se está correta ou não) em tempo polinomial.

Estes são chamados de problemas de “tempo polinomial não determinista” ou problemas NP (do inglês “Nondeterministic Polynomial time”). Isto é tal como o Sudoku — leva muito tempo para resolver um, mas depois é fácil verificar se está tudo certo.

Existem soluções P para problemas NP, mas não sabemos definitivamente se todos os problemas NP têm uma solução P, ou se jamais algum pode ser resolvido em P.

Se alguém conseguir provar que P = NP, terá descoberto algoritmos de tempo polinomial para diversos problemas. A própria ideia de um problema NP é a base da criptografia moderna — ou seja, gerar chaves de segurança fáceis de verificar, mas difíceis de decifrar.

Os computadores quânticos deveriam, em teoria, ser bem mais avançados que os clássicos, mas ainda não alcançaram as expectativas dos investigadores de pelo menos resolver as classes mais difíceis de problemas NP. Isto significa que o detentor da solução desta equação seria mais inteligente do que um computador quântico e poderia resolver diversos problemas matemáticos.

PARTILHAR

3 COMENTÁRIOS

RESPONDER

O Nepal proibiu, mas mulheres continuam a ser forçadas a dormir em "cabanas menstruais"

"Chaupadi" é uma tradição hindu, característica do Nepal, que força as mulheres a dormirem num abrigo quando estão menstruadas por serem consideradas impuras. Segundo o IFLScience, uma nova investigação mostra que 77% das raparigas que vivem …

O golo "doloroso" de Ansu Fati que fez dele o mais jovem jogador a marcar na Champions

Ansu Fati, avançado do Barcelona, tornou-se no mais jovem jogador de sempre a marcar um golo na Liga dos Campeões. Com 17 anos e 40 dias de idade, o espanhol faz mais uma vez história …

Almeida Henriques suspeito de receber avença enquanto esteve no Governo por favores a empresário

Almeida Henriques, antigo secretário de Estado Adjunto da Economia e Desenvolvimento Regional do Governo de Passos Coelho, e atual presidente da Câmara de Viseu, é suspeito de ter recebido dinheiro por favores ao empresário Agostinho …

Costa responde a Ventura: Programa do Governo não muda "semana sim semana não"

Recorrendo à ironia, o primeiro-ministro, António Costa, respondeu esta terça-feira ao deputado único do Chega, afirmando que o programa do Governo não muda "semana sim, semana não" consoante as críticas. No debate quinzenal na Assembleia da …

Pela primeira vez, porcos nascem com células de macaco (e morrem uma semana depois)

Pela primeira vez, cientistas chineses criaram pequenos leitões com órgãos que continham células de macaco. Os animais acabaram por morrer todos no espaço de uma semana. Os investigadores travam uma longa batalha para vir a desenvolver …

Iniciativa Liberal anuncia voto contra OE2020

O deputado único e presidente da Iniciativa Liberal (IL) anunciou esta terça-feira que o partido votará contra o Orçamento do Estado para 2020, depois de uma reunião com o Governo. "Este orçamento vai dar corpo ao …

Funcionários admitidos até 2005 podem perder férias se estiverem de baixa prolongada

Os funcionários públicos admitidos antes de 2006 e que estiverem de baixa por doença superior a 30 dias podem vir a perder dias de férias, segundo uma proposta do Governo ainda em negociação com os …

Tiroteio num supermercado em Nova Jersey faz seis mortos

As autoridades de Nova Jersey, nos Estados Unidos, informaram que o tiroteio registado num supermercado, esta terça-feira, causou seis mortos, entre os quais um polícia e dois suspeitos da autoria dos disparos. Os disparos foram ouvidos …

Atividade das amígdalas cerebelosas associada a comportamentos de bullying nos jovens

Certos padrões na atividade cerebral dos adolescentes, nomeadamente nas amígdalas cerebelosas, foi associada a comportamentos de bullying. Estes jovens revelaram ser menos empáticos perante rostos temerosos. O bullying é um problema social que afeta muitas crianças …

Já se sabe o que provocou o colapso violento do Kilauea

A erupção de 2018 em Kilauea, no Havai, caracterizou o espetacular colapso da caldeira do vulcão. Agora, novas investigações constatam que esta mudança dramática foi desencadeada por um pequeno derrame de magma do reservatório abaixo …