A OpenAI publicou um artigo de matemática cujo título afirma que a Exponential Time Hypothesis é falsa. Se a prova se sustentar, ela derruba uma das premissas de trabalho da ciência da computação teórica moderna: a de que os quebra-cabeças lógicos mais difíceis de um tipo padrão não podem ser resolvidos muito mais rápido do que testando todas as possibilidades. Um grande número de resultados de dificuldade publicados se apoia nessa hipótese, então uma refutação confirmada obrigaria a repensar todo o campo.
O artigo, datado de 17 de outubro e revisado em 25 de outubro de 2026, está no repositório público de matemática da OpenAI no GitHub e é atribuído só à OpenAI, sem autores individuais. O repositório diz que seus manuscritos foram produzidos por um modelo interno da OpenAI sem nome e devem ser tratados como dados brutos de pesquisa, não como artigos acabados. Ao longo de mais de 60 páginas, o teorema principal apresenta um algoritmo determinístico que conta todas as atribuições que satisfazem uma fórmula k-CNF, uma fórmula lógica formada por cláusulas de no máximo k termos, para qualquer k fixo igual ou maior que 2. O tempo de execução cresce aproximadamente como 2 elevado a n dividido pela raiz quadrada de log n, em que n é o número de variáveis, e o uso de memória continua polinomial. Isso é mais lento que tempo polinomial, mas mais rápido que qualquer 2 elevado a uma constante vezes n, que é justamente o que a hipótese exclui. Contar soluções é mais difícil do que decidir se existe alguma, então o resultado também refuta a versão de contagem da hipótese e, segundo o artigo, suas variantes mais fortes.
O método é algébrico. Pela nossa leitura da introdução, ele divide as variáveis em grupos, transforma a fórmula em equações polinomiais de grau baixo e conta seus zeros comuns usando interpolação e somas rápidas, partindo de técnicas anteriores de dividir e listar e de inclusão-exclusão. O artigo lista consequências: contagem exata subexponencial de colorações de grafos, conjuntos independentes e emparelhamentos perfeitos, e esquemas de aproximação para Max-k-SAT. Ele faz questão de dizer que isso não gera algoritmos rápidos para todo problema NP, porque limites de tempo desse formato não se transferem por reduções comuns.
O contexto exige cautela. Os melhores contadores exatos anteriores para 3-SAT ainda rodavam em tempo claramente exponencial, e décadas de trabalho, incluindo o algoritmo PPSZ e seus refinamentos, só baixaram a base do expoente aos poucos. Um dos corolários do artigo também depende de outro preprint da OpenAI, The Unique Games Theorem, de setembro, que também não foi revisado.
Nada disso passou por revisão por pares, o próprio repositório da OpenAI avisa que resultados sem uma prova formal em Lean podem conter erros, e não vimos respostas publicadas de especialistas em complexidade. Resultados desse porte já foram anunciados e retirados antes, muitas vezes por uma lacuna que só apareceu depois que especialistas revisaram cada lema. A postura certa por enquanto é interesse sem crença: o artigo é detalhado o bastante para que especialistas o confiram passo a passo, e o veredito deles resolverá a questão mais rápido do que qualquer comentário.