Um prêmio de $ 1.000.000 (£ 773.100) pode ser seu se você conseguir resolver este quebra-cabeça de xadrez aparentemente "simples".
O Clay Mathematics Institute (CMI) na América está oferecendo o prêmio em dinheiro para qualquer um que possa criar um programa de computador para resolver um problema conhecido como quebra-cabeça da rainha, inventado pela primeira vez em 1850, que é uma forma do que é conhecido como Problema P vs NP.
O quebra-cabeça parece bastante simples; coloque oito rainhas no tabuleiro de forma que duas rainhas não possam se atacar. A reviravolta, no entanto, é que os pesquisadores querem que o algoritmo funcione em um tabuleiro de xadrez de 1.000 por 1.000 quadrados. À medida que o número de quadrados aumenta, também aumenta o número de rainhas que você precisa colocar.
Pelas estimativas atuais, colocar 1.000 rainhas em um tabuleiro de 1.000 por 1.000 quadrados pode levar milhares de anos – devido ao grande número de possibilidades a serem consideradas.
Qualquer algoritmo capaz de resolver o quebra-cabeça rapidamente também seria capaz de quebrar as medidas de segurança online mais difíceis, disseram os pesquisadores, porque seria incrivelmente poderoso.
É um exemplo de Problema do Prêmio do Milênio, dos quais há sete no total. Esses quebra-cabeças foram anunciados em uma reunião em 2000 e dizem que representam os problemas mais difíceis enfrentados pela matemática. O CMI disse que isso era para mostrar às pessoas que ainda havia muitas perguntas sem resposta em matemática.
O Conselho de Administração do CMI designou um prêmio de $ 7 milhões para as soluções dos problemas, com $ 1 milhão alocado para a solução de cada problema. O primeiro deles foi resolvido em 2003 por Grigori Perelman, um matemático russo, mas ele recusou o prêmio.
A Universidade de St Andrews lançou um desafio para qualquer pessoa resolver esse quebra-cabeça usando um computador.
O professor da Universidade de St Andrews, Ian Gent, teve a ideia depois de ser desafiado por um amigo do Facebook a resolver o quebra-cabeça de xadrez sozinho. Ele e seus colegas Dr. Peter Nightingale e Dr. Christopher Jefferson tentaram escrever um programa de computador por conta própria.
Suas soluções usam 'backtracking' - um algoritmo usado na programação onde todas as opções possíveis são considerados e depois "recuados" até que a solução correta seja encontrada - e suas ideias sejam delineadas em um papel, publicado no Jornal de Pesquisa em Inteligência Artificial.
No entanto, assim que o tabuleiro de xadrez ficou grande o suficiente – 1.000 por 1.000 quadrados – o algoritmo não conseguiu lidar. Esses problemas são muito difíceis para os programas de computador porque há muitas opções a serem consideradas e isso pode levar muitos anos.
“Se você pudesse escrever um programa de computador que resolvesse o problema muito rapidamente, poderia adaptá-lo para resolver muitos dos problemas mais importantes que nos afetam diariamente”, disse o professor Gent. “Isso inclui desafios triviais, como descobrir o maior grupo de amigos do Facebook que não conheçam uns aos outros, ou muito importantes como decifrar os códigos que guardam todas as nossas transações online seguro."
“Na prática, ninguém jamais chegou perto de escrever um programa que pudesse resolver o problema rapidamente”, disse o Dr. Nightingale. “Então, o que nossa pesquisa mostrou é que – para todos os propósitos práticos – isso não pode ser feito.”
