OpenAI e Anthropic dizem que seus modelos refutaram uma hipótese central da computação

A OpenAI publicou soluções para três problemas matemáticos de longa data, entre elas uma refutação surpreendente da Hipótese do Tempo Exponencial (ETH, na sigla em inglês), uma suposição fundamental da ciência da computação sobre o quão difícil é resolver certos problemas. Como em divulgações anteriores do laboratório, a reação misturou entusiasmo e desconforto: o matemático da Anthropic Levent Alpöge argumentou que as soluções da OpenAI se apoiavam em trabalhos já existentes, e horas depois a Anthropic publicou sua própria refutação da ETH.

Dessa vez, a OpenAI variou sua divulgação por área: publicou os resultados matemáticos no GitHub, ofereceu aos cientistas da computação um grupo de trabalho e financiamento para uma conferência sobre as provas, e deixou que os físicos formassem seu próprio grupo de trabalho para decidir como divulgar seu resultado. A mudança veio após críticas do professor do MIT Ryan Williams, que lidera a resposta da área de ciência da computação e já havia comparado um despejo anterior de provas da OpenAI em outubro a um ataque de negação de serviço contra matemáticos. Ainda assim, Williams aceitou ajudar a interpretar o novo resultado, junto com Russell Impagliazzo e Ramamohan Paturi, da UC San Diego, que publicaram o artigo original da ETH em 1999; o primeiro passo do grupo foi uma carta aberta pedindo à comunidade opiniões sobre a matemática e sobre as normas para contribuições da IA a esse trabalho.

A ETH está dentro de uma questão mais ampla, conhecida como P versus NP: se todo problema cuja solução é fácil de verificar (NP) também é fácil de encontrar (P), a lógica por trás da criptografia, em que ler uma mensagem já decifrada é trivial, mas quebrar o código não é. A maioria dos cientistas supõe que P não é igual a NP, e a ETH reforçava essa suposição ao afirmar que nenhum algoritmo consegue resolver uma classe específica de quebra-cabeças lógicos difíceis sem que o tempo necessário cresça de forma exponencial à medida que o quebra-cabeça cresce. A OpenAI e a Anthropic afirmam que seus modelos produziram algoritmos capazes de resolver esses quebra-cabeças em tempo “subexponencial”, mais rápido do que se pensava possível, e que, se o resultado se confirmar, refutaria a ETH e poderia abrir caminho para provar que P é igual a NP.

“É provável que todo cientista da computação deva dar um pouco mais de peso à plausibilidade de que P = NP, embora esse peso possa variar”, disse Williams, acrescentando que duvida que o algoritmo da OpenAI seja o melhor que existe. O resultado ameaça colocar em xeque uma década de estudos construídos sobre a durabilidade da ETH, razão pela qual Williams pressionou a OpenAI a financiar uma conferência sobre as consequências. Ele também levantou uma preocupação mais imediata: se um algoritmo mais rápido quebra sistemas criptográficos que dependem de determinados tamanhos de chave. Disse que levou essa pergunta diretamente a Dan Roberts, responsável científico da OpenAI, e que o laboratório verificou e respondeu com confiança razoável de que nada havia sido quebrado. Williams diz que continua otimista quanto ao papel cada vez maior da IA na pesquisa, mesmo que isso obrigue os cientistas a elevar o nível das perguntas que fazem.

Por que importa

Se os algoritmos “subexponenciais” resistirem ao escrutínio, uma década de estudos construídos sobre a durabilidade da ETH, e possivelmente alguns sistemas criptográficos que dependem dela, vai precisar ser revisada, o que evidencia a velocidade com que os laboratórios de IA já conseguem desestabilizar campos considerados fundamentais.