geralt / Pixabay
As técnicas aplicadas pelos cientistas permitiram uma enorme redução no tempo que o computador precisou para decifrar o problema.
Quando um problema matemático fica sem resolução durante décadas, geralmente a resposta costuma ser uma equação complexa que precisa de páginas e páginas para ser explicada.
Desta feita, foi descoberta a solução para um problema que nasceu em 2002 — e a resposta é 15. O problema consistia em preencher uma grade com números de forma a que a distância entre quaisquer dois quadrados que tenham o mesmo número seja maior do que esse número.
A dúvida era saber qual era o número mais pequeno de números preciso para se completar a sequência infinita. Para resolver o problema, o estudante Bernardo Subercaseaux e o professor Marijn Heule, ambos da Universidade Carnegie Mellon, procuraram formas eficientes de descobrir soluções para problemas matemáticos complexos e demorados.
“Tínhamos várias ideias promissoras. Portanto, adotamos a mentalidade de ‘Vamos tentar otimizar a nossa abordagem até que possamos resolver este problema em menos de 48 horas de computação no cluster’”, disse Subercaseaux à Quanta Magazine.
Um dos primeiros grandes avanços que alcançaram foi descobrir que o valor tinha que ser maior que 12 e que não podia ser maior que 15, uma revelação que já tinha sido feita em vários estudos anteriores.
Já com um pequeno leque de respostas possíveis, os cientistas procuraram começar a reduzir o tempo computacional requerido para descobrir a solução. O primeiro passo foi explorar a simetria, tratando todas as soluções simétricas como equivalentes, o que reduziu o tempo por um fator de oito.
A dupla aplicou depois uma técnica de Heule a que ele chamou “crie cubos e conquiste” que permitiu descartar o 13 como a solução em menos de dois dias de exercícios de computação. Ou seja, já só restavam o 14 e o 15 como opções.
Para fazer isto, a dupla precisaria de otimizar as suas técnicas de computação por um fator de aproximadamente 100. A chave estava em considerar pequenas regiões da grade em vez de células individuais: em vez de considerar o problema quadrado por quadrado, consideraram-no em grupos de cinco quadrados de uma só vez.
No final, com este ajuste, o computador descartou o 14 como resposta ainda mais rápido do que o 13. “Tínhamos provado que 14 cores não eram suficientes! Muito empolgante! χρ(Z2) = 15!”, explica Subercaseaux.
Os cientistas estão ainda muito orgulhosos das técnicas que aplicaram. “Para um ponto de referência sobre o que otimizamos, em 2010, Ekstein et al. provou um limite inferior de 12 e precisou 120 dias de computação. As nossas técnicas permitem-nos obter o mesmo limite inferior em menos de 10 segundos”, escreveu Subercaseaux.
A pesquisa está disponível para consulta pré-publicação no arXiv.
