Cientistas da Clay Mathematics Institute, nos Estados Unidos, estão oferecendo US$ 1 milhão (R$ 3,1 milhão) para quem for capaz de resolver uma nova versão do clássico problema das oito rainhas. A ideia é desenvolver um sistema de computador que calcule rapidamente as probabilidades de resolução do enigma, mesmo com números muito grandes.
Problema das oito rainhas
O enigma consiste em conseguir colocar oito rainhas em um tabuleiro de 8×8 de modo que nenhuma ameace a outra. A dificuldade está no fato de que, como a peça mais poderosa do jogo, a rainha pode se mover na horizontal, na vertical e na diagonal e andar quantas casas desejar.
Pode parecer difícil, mas na realidade há 92 opções (das 4,5 bilhões de probabilidades) de solução para esse problema.
O mistério de 1 milhão de dólares
Há variáveis do problema, como, por exemplo, quantas são as possibilidades se colocarmos 20 rainhas em um tabuleiro de 20×20? E 100? Essa questão originou o problema das N-rainhas, no qual N é igual ao número de rainhas, assim como do tamanho do tabuleiro (NxN).
Um número não tão alto quanto 1000 já resulta em algo quase impossível de ser calculado por um computador, pelo número gigantesco de possibilidades. A situação fica ainda mais complicada quando algumas das rainhas são “fixadas” e deve-se dispor as outras peças a partir daí.
O problema pode ser fácil de entender, mas descobrir maneiras de resolvê-lo — para qualquer valor de N — é, na verdade, um dos fatos mais difíceis na complexidade computacional. “Se você pudesse escrever um programa de computador que pudesse resolver o problema muito rápido, você poderia adaptá-lo para resolver muitos dos enigmas mais importantes que nos afetam diariamente”, afirma Ian Gent da Universidade de St Andrews, no Reino Unido.
Gent conta que um programa desse abriria caminhos para desvendarmos desafios triviais, como descobrir o maior grupo de seus amigos do Facebook que não se conhecem, ou muito importantes, como desvendar os códigos que mantêm todas as transações online seguras.
A contribuição técnica do artigo recentemente publicado é que o Problema das N-rainhas está na classe de enigmas matemáticos conhecidos como NP-Complete, explica Gent. “Se correto, isso significa que qualquer algoritmo que possa resolver o problema [das rainhas] pode ser usado indiretamente para resolver qualquer outro problema na classe NP”, relata.
O prêmio
Por isso o instituto resolveu premiar com 1 milhão de dólares quem conseguir resolver o mistério criando um algoritmo que chegue a resultados em um tempo relativamente curto — ou quem provar que é impossível encontrar essa “fórmula secreta”.
Alguns especialistas acreditam que milhares de anos serão necessários para alguém resolver o mistério, enquanto alguns nem acham que isso seja possível. “Na prática, ninguém chegou perto de escrever um programa que possa resolver o problema rapidamente. Então, o que nossa pesquisa mostrou é que — para todos os propósitos práticos — não pode ser feito”, contou em comunicado oficial Peter Nightingale, membro do estudo.
Fonte: revista Galileu / com informações de Science Alert
