OpenAI afirma que sua IA refutou uma hipótese de 1999 sobre a velocidade de resolução de problemas complexos
A OpenAI afirmou que seu modelo encontrou um algoritmo para problemas complexos, como sudoku, grades de horários e o caixeiro-viajante, que contradiz a hipótese do tempo exponencial (ETH), formulada em 1999. A hipótese dizia que, a cada nova variável, o tempo de resolução no pior caso dobra, enquanto o algoritmo da OpenAI cresce mais devagar. A prova em formato Lean está no GitHub, e qualquer pessoa pode verificá-la. Por enquanto, trata-se apenas de uma afirmação da empresa, e seu planejador não ficará mais rápido por causa disso.
Processado por IA de TG: @hiaimedia (Hi, AI • Новости технологий); editado por Hamidun News
Imagine que você está escrevendo um planejador de turnos para um armazém ou um roteirizador para entregadores. Quanto mais pedidos e condições, mais lento o programa fica, e em algum momento ele simplesmente não consegue dar conta. A ciência da computação se pergunta há muito tempo: isso é uma falha dos nossos algoritmos ou um limite do próprio problema? A OpenAI afirmou que seu modelo interno encontrou um algoritmo que refuta uma das principais hipóteses sobre o tema. Por enquanto, trata-se apenas de uma afirmação, e a seguir vamos analisar o que já está claro e o que ainda não está.
Sobre o que é a disputa e o papel do sudoku
A hipótese do tempo exponencial (ETH) surgiu em 1999. Ela trata de uma grande classe de problemas combinatórios, nos quais a solução é fácil de verificar, mas difícil de encontrar. O sudoku é um bom exemplo: conferir se os números estão corretamente posicionados leva um minuto. Resolver um tabuleiro desses com rapidez é muito mais difícil, especialmente quando ele cresce de 9×9 para 1000×1000. A essa mesma classe pertencem a montagem de horários, o problema do caixeiro-viajante e milhares de outras tarefas de logística, planejamento e otimização.
Se você testar as opções uma a uma, o tempo máximo de execução dobra a cada nova variável. Para ilustrar: se 50 condições exigem uma hora, 51 exigirão duas, e 52, quatro. Existem métodos mais sofisticados que funcionam um pouco mais rápido. Mas a ETH afirmava que, no pior caso, o tempo continuaria crescendo de forma exponencial. Segundo a OpenAI, o algoritmo encontrado por seu modelo cresce mais devagar do que uma exponencial. É isso que contradiz a hipótese.
Como isso será verificado
A prova está escrita em Lean e publicada no GitHub. Lean é um sistema de verificação formal: ele checa por máquina cada passo do raciocínio, e não é preciso confiar na palavra do autor. Qualquer interessado pode executar a verificação em seu próprio computador. O grupo de avaliadores será liderado pelo professor Ryan Williams, do MIT, e pelos dois autores da própria hipótese, Russell Impagliazzo e Ramamohan Paturi. Ou seja, o resultado será avaliado por quem melhor entende o que precisaria ser refutado.
A cautela é compreensível. No início de outubro, a OpenAI publicou 722 artigos sobre problemas matemáticos em aberto. Menos de um dia depois, três trabalhos tiveram de ser retirados por causa de um erro. Parte dos matemáticos criticou essa abordagem. O ganhador da Medalha Fields Terence Tao chamou de "lixo tóxico" as provas que empresas de IA produzem em massa na corrida por benchmarks. Nesse contexto, o novo trabalho, com uma formalização em Lean, parece bem mais sério, mas a confirmação ainda precisa chegar.
O que isso muda para quem trabalha na prática
Centenas de trabalhos em teoria dos grafos, biologia computacional e bancos de dados se apoiam na ETH. Muitos deles provam que certos problemas não podem ser resolvidos abaixo de determinado limite de tempo. Se a refutação for confirmada, essas conclusões perderão seu fundamento, e os teóricos terão de rever parte de seus resultados.
Mas não convém exagerar o efeito. A refutação da ETH não gera, por si só, algoritmos rápidos para esses problemas; eles precisarão ser buscados separadamente. Por isso, os desenvolvedores de planejadores, solvers e otimizadores não têm motivo para reescrever seu código hoje: a busca de horários do seu sistema não ficará mais rápida.
A história deixa duas lições práticas:
- Quando a IA produz um resultado complexo, seja uma prova ou um código, o mais importante é saber se ele pode ser verificado por máquina. Formatos como o Lean transformam "parece convincente" em "verificado".
- A geração ficou barata, mas a verificação continua cara. Os três trabalhos retirados em menos de um dia mostram que o gargalo não será o modelo, e sim a equipe que confere as conclusões dele.
Se Williams, Impagliazzo e Paturi encontrarem uma falha na prova, a história terminará com mais uma retratação. Se não encontrarem, a IA terá refutado pela primeira vez uma hipótese sobre a qual se construíram centenas de trabalhos em teoria da complexidade.
- Verificação liderada por Ryan Williams (MIT) e pelos autores originais da hipótese
- Prova formal em Lean publicada no GitHub
- Três dos 722 artigos da OpenAI retirados no início de outubro
- 21 de nov. de 2026OpenAI GPT-6 Cyber encontrou cerca de 35 falhas no iPhone, no Mac e em outros dispositivos da Apple
- 21 de nov. de 202622 agentes Claude passaram seis semanas atrás de respostas sobre buracos negros e resolveram dois problemas
- 21 de nov. de 2026Google vai separar o armazenamento de chats do treinamento do Gemini: dá para recusar sem perder o histórico
- 21 de nov. de 2026Apple dá a usuários do macOS 27.3 beta 2 como limitar o acesso de agentes de IA aos arquivos do Mac
Perguntas frequentes sobre a notícia
O que se sabe sobre Sobre o que é a disputa e o papel do sudoku?
A hipótese do tempo exponencial (ETH) surgiu em 1999. Ela trata de uma grande classe de problemas combinatórios, nos quais a solução é fácil de verificar, mas difícil de encontrar. O sudoku é um bom exemplo: conferir se os números estão corretamente posicionados leva um minuto. Resolver um tabuleiro desses com rapidez é muito mais difícil, especialmente quando ele cresce de 9×9 para 1000×1000.
Como isso será verificado?
A prova está escrita em Lean e publicada no GitHub. Lean é um sistema de verificação formal: ele checa por máquina cada passo do raciocínio, e não é preciso confiar na palavra do autor. Qualquer interessado pode executar a verificação em seu próprio computador. O grupo de avaliadores será liderado pelo professor Ryan Williams, do MIT, e pelos dois autores da própria hipótese, Russell Impagliazzo e Ramamohan Paturi. Ou seja, o resultado será avaliado por quem melhor entende o que precisaria ser refutado.
O que isso muda para quem trabalha na prática?
Centenas de trabalhos em teoria dos grafos, biologia computacional e bancos de dados se apoiam na ETH. Muitos deles provam que certos problemas não podem ser resolvidos abaixo de determinado limite de tempo. Se a refutação for confirmada, essas conclusões perderão seu fundamento, e os teóricos terão de rever parte de seus resultados. Mas não convém exagerar o efeito. A refutação da ETH não gera, por si só, algoritmos rápidos para esses problemas; eles precisarão ser buscados separadamente.
Test Frontier LLMs & Autonomous Agents in One Workspace
Run Claude Opus 5.5, GPT-6, Gemini 3.1, and DeepSeek side-by-side in Nomad AI (nomadnet.ai) — unified model routing, deep research, and multimodal workflows under one subscription.
O essencial da IA — uma vez por semana
Sete histórias que realmente importaram, escolhidas a dedo. Sem ruído nem releases.
Pronto! Verifique seu e-mail para a confirmação.