Intensivo Grátis 21–22/11Intensivo gratuito de 2 dias em Vibecoding (21–22/11 às 16:00 MSK) · Turma 3 começa 23/11Inscrever-se grátis →Turma 3 (23/11)

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
OpenAI afirma que sua IA refutou uma hipótese de 1999 sobre a velocidade de resolução de problemas complexos
Fonte: TG: @hiaimedia (Hi, AI • Новости технологий). Colagem: Hamidun News.
Ouvir artigo
Ficha técnica e números-chave
ParâmetroDados
Fonte originalTG: @hiaimedia (Hi, AI • Новости технологий) ↗
Editor-chefe
Dado-chave #1A verificação será liderada por Ryan Williams, do MIT, e por dois autores da ETH
Dado-chave #2A ETH sustenta centenas de trabalhos em grafos, biologia e bancos de dados
Dado-chave #3No início de outubro, três dos 722 artigos da OpenAI foram retirados por causa de um erro

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
História

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.

ZK
Zhemal Khamidun — CPO da Alpina Digital, gerente de produto do AlpinaGPT. Cria produtos de IA desde 2019. O Hamidun News é um projeto pessoal que virou um agregador em produção com mais de 6.000 leitores.
✦ Unified AI Workspace · Nomad

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.

Try Nomad AI →Launch Nomad Agent
O que você acha?
Carregando comentários…