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

Cientistas produziram um processador quântico em larga escala feito apenas de luz

Uma equipa internacional de cientistas da Austrália, Japão e Estados Unidos produziu um protótipo de um processador quântico em larga escala feito apenas de luz laser. O mais recente processador quântico é baseado num projeto com …

FIFA investe 449 milhões de euros para desenvolver o futebol feminino

A FIFA anunciou que vai investir 500 milhões de dólares no desenvolvimento do futebol feminino. Em cima da mesa está uma Liga das Nações, um mundial de clubes e torneios para camadas jovens. A FIFA vai …

Escritor famoso escreve livro para ser lido apenas em 2114

O famoso escritor norueguês Karl Ove Knausgaard, autor de romances como A Morte do Pai e a Ilha da Infância, onde explora a sua história pessoal e o seu dia a dia, aceitou escrever um …

PS deverá aprovar recandidatura de Ferro à presidência da Assembleia da República

O Grupo Parlamentar do PS vai reunir-se na quinta-feira, com a presença do secretário-geral, António Costa, ocasião em que deverá aprovar a recandidatura de Ferro Rodrigues ao cargo de presidente da Assembleia da República. Fonte oficial …

Perito revela que arma que investigação diz que matou Luís Grilo foi adulterada

O perito que examinou a arma que, segundo o Ministério Público, António Joaquim usou para matar o triatleta Luís Grilo revelou hoje em tribunal que o revólver foi adulterado, não conseguindo garantir se essa foi …

Cientistas criam vasos sanguíneos artificiais funcionais

Cientistas nos Estados Unidos usaram impressão 3D para fabricar vasos sanguíneos funcionais que poderão vir a ser usados clinicamente em casos de doenças vasculares. O resultado das experiências é relatado num estudo publicado esta terça-feira no …

Ordem suspende durante seis meses obstetra do caso do bebé sem rosto

O Conselho Disciplinar do Sul da Ordem dos Médicos decidiu suspender preventivamente o obstetra envolvido no caso do bebé que nasceu em Setúbal com malformações graves. A informação foi avançada à Lusa por fonte oficial da …

A China está a criar porcos gigantes (tão grandes como ursos polares)

https://vimeo.com/368036025 Porcos tão pesados como ursos polares. Esta é a solução encontrada por produtores chineses de porcos que tentam resolver o problema da falta de carne no mercado, muito por culpa da gripe suína africana dizimou …

Rússia e Síria vão partilhar controlo do nordeste sírio

O Presidente turco Recep Tayyip Erdogan disse hoje que a Turquia e a Rússia alcançaram um acordo pelo qual as forças curdas da Síria vão recuar 30 quilómetros a partir da zona fronteiriça do nordeste …

Câmara dos Comuns aprova acordo do Brexit (mas rejeita calendário apertado)

A Câmara dos Comuns aprovou esta terça-feira a primeira votação do acordo para o Brexit. No entanto, a calendarização da saída foi rejeitada numa segunda votação, deixando um impasse na data para o Brexit. Pela primeira …