Análise
OpenAI e Anthropic dizem que a IA refutou a hipótese do tempo exponencial, mas a prova não está certificada e o ganho só começa com entradas astronómicas
OpenAI e Anthropic dizem que a IA refutou a hipótese do tempo exponencial. Impagliazzo fala em notícia chocante, mas a revisão continua em curso.
Russell Impagliazzo, que co-propôs a hipótese do tempo exponencial (ETH) nos anos 1990, chamou de notícia muito chocante a sua refutação produzida por IA, segundo a imprensa retransmitida pela AI Weekly a 7 de novembro. O enquadramento pede cautela: dois artigos, um da OpenAI e outro da Anthropic, anunciados a 26 de outubro, afirmam um algoritmo mais rápido para 3-SAT; os revisores dizem que a sua participação não é uma certificação, o resultado não resolve P contra NP e o ganho só supera a força bruta com tamanhos de entrada muito além do armazenável. Transparência: a Anthropic desenvolve o Claude, que ajuda a redigir artigos deste site, e publicou um dos dois artigos.
O essencial
- A afirmação: o artigo da OpenAI (67 páginas) e o da Anthropic (49) apresentam algoritmos de 3-SAT em tempo 2^o(n), o que contrariaria a ETH. Ambos dizem que a IA participou muito e que as provas foram verificadas em Lean, segundo a AI Weekly.
- O que dizia a ETH: 3-SAT não se resolve em tempo subexponencial. É mais forte do que P diferente de NP e serve para mostrar que muitos algoritmos são quase ótimos, segundo a Wikipedia.
- Verificação até agora: um grupo com Impagliazzo, Ryan Williams e Ramamohan Paturi examinou o trabalho. A declaração conjunta diz que a participação não deve ser tomada como certificação, e Williams falou de partes de aspeto estranho que a comunidade precisa de estudar.
- Alcance prático: estimativas externas colocam o ponto de equilíbrio com a força bruta perto de 10^2.389 variáveis para o limite da OpenAI e 10^10.000 para o caso de cinco cláusulas da Anthropic. Os solucionadores SAT atuais e a cifragem não são afetados.
O que está e não está demonstrado
Um algoritmo subexponencial não é polinomial, por isso ambos os laboratórios dizem que o resultado não resolve P contra NP, e a OpenAI esclarece que a aceleração não se estende aos problemas NP em geral. A verificação em Lean confirma a lógica de um enunciado formal, mas os revisores pediram os dados brutos e uma conferência, que a OpenAI aceitou financiar, segundo a AI Weekly. Datas relatadas: a IA encontrou o argumento em linguagem natural a 16 de outubro, foi formalizado no dia seguinte e os artigos saíram a 26 de outubro.
Chips e cifragem: o que está estabelecido
A ETH trata do pior caso, pelo que o efeito imediato é teórico e atinge os limites inferiores que dela dependem. Falar de verificação de chips mais rápida ou de cifragem enfraquecida é especulação de longo prazo. A BeInCrypto e a Let's Data Science dizem que a criptografia atual e os solucionadores industriais não são afetados, e a AI Weekly retransmite um informático que considera enganador um artigo de imprensa. A HackerNoon diz que os autores aplicam também o método a curvas elípticas no papel; não vimos isso verificado.
O que não está estabelecido
- Certificação das provas pelo grupo de revisão: pendente, segundo a AI Weekly.
- Qualquer aceleração utilizável em instâncias SAT reais: não demonstrada; os limiares são astronómicos.
- Qualquer ataque prático à cifragem ou às ferramentas de projeto de chips: não estabelecido.
- Se as afirmações do Wall Street Journal e do New York Times sobre chips e cifragem vão além da especulação: não as lemos diretamente.
Tabela-resumo
| Ponto | O que está declarado em 7 de novembro de 2026 | Fonte |
|---|---|---|
| Anúncio | Dois artigos anunciados a 26 de outubro de 2026 (OpenAI 67 páginas, Anthropic 49) | AI Weekly |
| Resultado afirmado | 3-SAT em tempo 2^o(n), verificado em Lean | AI Weekly |
| Tamanho de equilíbrio | Cerca de 10^2.389 variáveis (OpenAI), 10^10.000 (caso de cinco cláusulas da Anthropic) | AI Weekly |
| Revisores | Impagliazzo, Williams, Paturi; declaração conjunta: não é certificação | AI Weekly |
| P contra NP | Não resolvido, segundo ambos os laboratórios | Let's Data Science |
Perguntas frequentes
A IA provou que P é igual a NP?
Não. O algoritmo afirmado é subexponencial, não polinomial, e ambos os laboratórios dizem que P contra NP não está resolvido.
A cifragem ficou mais fraca?
Não na prática. Os meios consultados dizem que a criptografia em uso não é afetada e o ganho só aparece com entradas absurdamente grandes.
A prova está confirmada?
Ainda não certificada. As provas foram verificadas em Lean, mas os revisores dizem que a sua participação não é certificação e o estudo continua.
Método e limites
Fontes verificadas a 8 de novembro de 2026. Não lemos os dois artigos, os ficheiros Lean nem os artigos de imprensa originais; apoiámo-nos na AI Weekly, Let's Data Science, HackerNoon, BeInCrypto e Wikipedia. Transparência: a Anthropic desenvolve o Claude, que ajuda a redigir artigos deste site. Não é aconselhamento de investimento nem de segurança.
Fontes
- AI Weekly: OpenAI's AI Disproof of 1998 ETH Shocks Co-Author Impagliazzo (verificado em 2026-11-08)
- Let's Data Science: OpenAI and Anthropic Broke a 1999 Conjecture. Both Found It on October 16. (verificado em 2026-11-08)
- HackerNoon: OpenAI and Anthropic claim AI has disproved a 27-year-old computer science hypothesis (verificado em 2026-11-08)
- BeInCrypto: OpenAI Says Its AI Refuted the Exponential Time Hypothesis. Is Bitcoin Safe? (verificado em 2026-11-08)
- Wikipedia: Exponential time hypothesis (verificado em 2026-11-08)
Encontrou um erro neste artigo? Avise-nos · Nossa política de correções