QUANTA MAGAZINE - Desde os primórdios da ciência da computação – uma área conhecida por sua abordagem metódica à solução de problemas –, a aleatoriedade tem tido um papel importante nela. O primeiro programa rodado no primeiro computador eletrônico de uso geral do mundo usou a aleatoriedade para simular processos nucleares. Metodologias semelhantes foram usadas desde então na astrofísica, climatologia e economia. Em todos esses casos, inserir números aleatórios em certas etapas do algoritmo ajuda os pesquisadores a explicar a indefinição das muitas maneiras pelas quais processos complexos podem acontecer.
Mas adicionar aleatoriedade a um algoritmo também pode ajudá-lo a calcular a resposta correta para perguntas com apenas duas possibilidades: verdadeiro ou falso. “Você apenas diz: ‘ok, deixa eu desistir, parar de tentar e só escolher alguma coisa aleatoriamente’”, disse Eric Blais, cientista da computação da Universidade de Waterloo. “Para muitos problemas, isso acaba sendo uma estratégia bem-sucedida.”
Leia também
Digamos que você queira verificar se um determinado número é primo (divisível apenas por um e ele mesmo) ou composto (tem mais de dois divisores). Você poderia simplesmente tentar dividi-lo por todos os fatores possíveis, mas, para números maiores, esse método de “força bruta” e outros algoritmos de fatoração são terrivelmente lentos. E se o número for composto, os algoritmos de fatoração dizem os valores de seus divisores – mais informações do que você queria. Caso esteja interessado apenas na “primalidade” de um número, existe um algoritmo mais eficiente?
Sim, se você usar a aleatoriedade. O conceito no qual ele se baseia remonta a um resultado do século 17 do matemático francês Pierre de Fermat, conhecido como “pequeno teorema de Fermat”. O matemático considerou dois números inteiros – vamos chamá-los de “N” e “x”. Ele provou que, se “N” é um número primo, então xN - x é sempre um múltiplo de “N”, independentemente do valor de “x”. De modo equivalente, se xN - x não é um múltiplo de “N”, então “N” não pode ser um número primo. Mas a afirmação inversa nem sempre é verdadeira: se xN − x é um múltiplo de “N”, então “N” costuma ser, mas nem sempre é, um número primo.
Para transformar o pequeno teorema de Fermat em um teste de primalidade, basta pegar o “N” que lhe interessa, escolher um “x” aleatório e aplicá-los na fórmula xN − x. Se o resultado não for um múltiplo de “N”, então a resposta está dada: você sabe que “N” é, sem dúvidas, um número composto. Se o resultado for um múltiplo de “N”, então “N” provavelmente é um número primo. Agora, escolha outro “x” aleatoriamente e teste mais uma vez. Na maioria dos casos, depois de algumas dezenas de tentativas, você pode concluir com quase certeza que “N” é um número primo. “Você faz isso um pequeno número de vezes e, de alguma forma, a probabilidade de haver um erro é menor do que a probabilidade de um asteroide atingir a Terra entre agora e quando você verificar a resposta”, disse Blais.
Os primeiros testes de primalidade usando algoritmos aleatórios (baseados em aperfeiçoamentos do pequeno teorema de Fermat) deram início a uma nova era. Após a resolução de cada problema, revelou-se muito mais fácil solucioná-los com aleatoriedade do que com algoritmos não aleatórios ou determinísticos. A chave era reformular cada problema como um que pudesse ser resolvido rapidamente dando um valor apropriado para algum número “x”, e então provar que quase qualquer “x” serviria. A solução funciona mesmo sem os pesquisadores saberem como determinar se uma escolha específica é boa ou não. Os matemáticos brincam dizendo que este desafio incomum é semelhante a procurar uma palha no palheiro.
Mas esses acertos fizeram com que os pesquisadores se perguntassem por que a aleatoriedade deveria ajudar com problemas como o teste de primalidade, que tem a ver com encontrar padrões ocultos e não aleatórios. “Há algo um pouco paradoxal nisso”, disse Rahul Santhanam, cientista da computação da Universidade de Oxford. “A mera aleatoriedade está ajudando a entender a estrutura que resolve o problema.”
Em 1994, os cientistas da computação Noam Nisan e Avi Wigderson ajudaram a resolver essa confusão ao demonstrar que a aleatoriedade, embora útil, provavelmente não era necessária. Eles provaram que de duas uma: ou todos os problemas que podiam ser resolvidos facilmente usando a aleatoriedade também tinham algoritmos determinísticos rápidos, ou muitos daqueles problemas conhecidos pela dificuldade eram, na verdade, fáceis. Os cientistas da computação consideram a segunda possibilidade muito improvável.
Aliás, os cientistas da computação muitas vezes acham mais fácil desenvolver um algoritmo determinístico começando com uma versão aleatória e, depois, retirando a aleatoriedade. “Assim que tenho o algoritmo, de repente percebo uma maneira muito óbvia de torná-lo determinístico”, disse Eli Upfal, cientista da computação da Universidade Brown. “Mas se eu não pensasse sobre ele de forma aleatória como uma questão probabilística, provavelmente não pensaria nisso.”
Quase 30 anos depois da demonstração histórica de Nisan e Wigderson, os algoritmos aleatórios continuam tão populares quanto antes, porque a retirada da aleatoriedade pode ser complicada e os algoritmos determinísticos costumam ser eficientes apenas na teoria. Foi apenas em 2022 que três pesquisadores descobriram um jeito de retirar a aleatoriedade do teste de primalidade, mas, na prática, o algoritmo deles é bem mais lento que os melhores algoritmos aleatórios. Para outros problemas, é difícil até mesmo saber por onde começar – o algoritmo mais conhecido tem um problema que lembra aquela velha questão de “quem veio primeiro: o ovo ou a galinha?” e do qual só se pode escapar por meio da aleatoriedade.
É o caso de uma descoberta recente na teoria dos grafos. No ano passado, três cientistas da computação desenvolveram um algoritmo rápido para encontrar o caminho mais curto em um grafo – uma teia de nós conectados por arestas – que funciona mesmo quando algumas arestas subtraem parte do comprimento total do caminho em vez de aumentá-lo. O algoritmo deles envolvia transformar o grafo em algo mais simples ao excluir certas arestas, resolvendo o problema para o grafo simplificado, e, depois, levando em consideração as arestas excluídas. Eles poderiam provar que o algoritmo seria executado rapidamente se nenhum caminho mais curto passasse por muitas arestas excluídas – caso contrário, a fase final demoraria demais.
Contudo, como decidir quais arestas excluir, para início de conversa? Não é apenas difícil encontrar o grupo ideal de arestas deterministicamente – é impossível. Ele depende de quais caminhos são mais curtos, o mesmo problema que os três investigadores estavam tentando resolver. Mas apesar de eles não terem encontrado o melhor grupo de arestas para excluir, conseguiram provar que a maioria das escolhas aleatórias seria muito boa, e isso foi o bastante para interromper o looping de autorreferência. Nos raros casos em que o algoritmo fez uma escolha infeliz e empacou na fase final, eles conseguiram simplesmente pará-lo e fizeram com que fosse rodado outra vez.
“A aleatoriedade é basicamente uma forma de garantir que algo seja verdadeiro sobre a solução ideal sem conhecer a solução ideal”, disse Aaron Bernstein, um dos autores do novo algoritmo.
A aleatoriedade tem inúmeros outros usos na ciência da computação, da criptografia à teoria dos jogos e ao aprendizado de máquina. Ao que tudo indica, ela veio para ficar. /TRADUÇÃO ROMINA CÁCIA
História original republicada com permissão da Quanta Magazine, uma publicação editorialmente independente apoiada pela Simons Foundation. Leia o conteúdo original em How Randomness Improves Algorithms