A OpenAI publicou um artigo de 67 páginas afirmando que a IA da empresa refutou a Hipótese do Tempo Exponencial (ETH). A conjectura data de 1999 e não tem nenhuma conexão com ethereum, o preço do ethereum ou o co-fundador Vitalik Buterin. A afirmação gerou discussões entre matemáticos e usuários de criptomoedas no X. Um usuário do X, Takumi, brincou: "Droga, os traders de algoritmo acabaram com o $ETH". Andrew Jiang escreveu: "Vitalik tem estado muito quieto desde que isso saiu."
Cientistas da computação Russell Impagliazzo, Ramamohan Paturi e Francis Zane propuseram a ETH. A conjectura afirma que resolver o problema lógico 3-SAT não pode ser muito mais rápido do que testar todas as combinações. O problema 3-SAT exige encontrar atribuições verdadeiro-falso que satisfaçam regras envolvendo três opções de cada vez. A OpenAI afirma que centenas de artigos dependem da ETH para estabelecer limites computacionais em teoria dos grafos, biologia computacional, bancos de dados e geometria. A OpenAI argumenta que refutar a ETH renova questões sobre possíveis melhorias de velocidade e pode direcionar a pesquisa para algoritmos melhores.
O artigo possui data de 17 de outubro e data de revisão de 25 de outubro. O artigo apresenta um algoritmo determinístico, que não utiliza aleatoriedade, para contar todas as atribuições satisfatórias em tempo subexponencial. Tempo subexponencial significa que o trabalho necessário aumenta mais lentamente do que qualquer função exponencial do número de variáveis. Contar atribuições satisfatórias é mais difícil do que determinar se alguma atribuição satisfatória existe, portanto, o algoritmo de contagem também resolve o problema de decisão. A OpenAI afirma que a IA descobriu a suposta refutação em 16 de outubro. A OpenAI afirma que o resultado foi formalizado em 17 de outubro usando Lean, um software que verifica mecanicamente cada passo lógico. O artigo e a formalização estão disponíveis no GitHub. A OpenAI também publicou 722 manuscritos matemáticos por meio do GitHub no início deste mês, mas apenas 162 incluíam um resultado principal verificado por computador.
Impagliazzo, Paturi e Ryan Williams do MIT estão liderando um exame independente da alegação. Os três pesquisadores alertaram em uma carta aberta que a participação não deve ser interpretada como certificação. Os pesquisadores disseram que uma descoberta de tamanha importância exige uma revisão independente rigorosa e uma explicação que outros pesquisadores possam reconstruir, desafiar e desenvolver. A OpenAI afirma que os participantes não são remunerados e não assinaram acordos de confidencialidade. A OpenAI concordou em liberar todos os dados brutos e financiar uma conferência sobre o resultado.
A OpenAI alerta que identificar algoritmos úteis e traduzir progressos teóricos em ganhos práticos exigirá pesquisas adicionais substanciais. O artigo não estabelece que todos os problemas NP admitem soluções em tempo subexponencial. P consiste em problemas que computadores podem resolver eficientemente, enquanto NP consiste em problemas cujas soluções propostas podem ser verificadas eficientemente. A questão P versus NP, que pergunta se a verificação eficiente sempre implica solução eficiente, permanece não resolvida.
A Anthropic publicou posteriormente um artigo atribuído ao Claude, intitulado "A 2^o(n) Time Algorithm for 3-SAT" e datado de 26 de outubro. O repositório acompanhante afirma que uma versão interna de pesquisa do Claude descobriu o algoritmo, que também aborda o ETH. O repositório alerta que o resultado diz respeito ao comportamento assintótico e não faz nenhuma afirmação sobre a resolução prática de fórmulas. O Claude formalizou o Último Teorema de Fermat usando Lean em setembro. O matemático Terence Tao alertou em setembro que até rumores de pesquisa sobre um problema podem provocar esforços extensivos assistidos por IA antes que o projeto original esteja plenamente desenvolvido.
A OpenAI contribuiu recentemente com US$ 5 milhões para a Simons Foundation. A contribuição apoiará workshops, conferências e programas especiais que ajudam pesquisadores a analisar e expandir os resultados produzidos por IA.