IA refuta a hipótese do tempo exponencial: o que tudo isso significa

OpenAI e Anthropic publicaram, cada uma, uma prova de que a hipótese do tempo exponencial é falsa.

A ETH é uma suposição de 27 anos na ciência da computação teórica que diz que alguns problemas nunca podem ser resolvidos muito mais rápido do que por força bruta. Agora, os principais laboratórios de IA dizem que isso simplesmente não é verdade.

Se as provas se mantiverem, serão o resultado mais significativo gerado por IA na ciência da computação até hoje. Elas também obrigam a repensar literalmente centenas de artigos que assumiam a ETH como verdadeira.

Neste artigo, explicamos o que a hipótese do tempo exponencial realmente significa, junto com P vs. NP, que é relacionada. Também veremos exatamente o que os dois laboratórios afirmam, como as provas foram verificadas e o que muda (e o que não muda) para a criptografia.

P vs. NP em termos simples

P versus NP pergunta se todo problema cuja resposta é fácil de verificar também é fácil de resolver. É um dos sete Problemas do Prêmio do Milênio e continua em aberto após esta notícia.

Um Sudoku é a ilustração clássica. Verificar uma grade preenchida leva segundos: basta escanear cada linha, coluna e bloco para ver se há repetições. Encontrar a solução a partir de uma grade quase vazia pode levar muito mais tempo, e essa diferença explode à medida que a grade cresce.

• P é a classe de problemas que um computador consegue resolver em tempo polinomial, ou seja, o trabalho cresce como n², n³ e assim por diante, conforme o tamanho da entrada n aumenta.
• NP é a classe de problemas cujas soluções propostas um computador consegue verificar em tempo polinomial.

Todo problema em P também está em NP. A questão em aberto é se a recíproca vale. A maioria dos cientistas da computação acredita que P ≠ NP, ou seja, que alguns problemas são fundamentalmente mais difíceis de resolver do que de verificar. A criptografia moderna se apoia nessa crença: criptografar é fácil, mas desfazer a criptografia sem a chave deve ser difícil.

O que é a hipótese do tempo exponencial?

A ETH é mais específica: afirma que um problema de NP em particular, o 3-SAT, precisa de tempo exponencial, não importa o quão esperto seja o algoritmo. Russell Impagliazzo e Ramamohan Paturi, da UC San Diego, a propuseram no fim da década de 1990, com Francis Zane contribuindo para o trabalho fundamental.

O problema 3-SAT

No 3-SAT, você recebe uma fórmula composta por n variáveis verdade/falso e uma lista de cláusulas. Cada cláusula junta três condições com OR, por exemplo "x₁ é verdadeira OU x₄ é falsa OU x₇ é verdadeira". A tarefa é encontrar uma atribuição às variáveis que satisfaça todas as cláusulas ao mesmo tempo.

A força bruta tenta todas as 2ⁿ atribuições, então cada variável extra dobra o trabalho. Dá para ver como, por volta de 100 variáveis, isso se torna inviável.

O que a ETH diz

A ETH afirma que existe uma constante c > 1 tal que nenhum algoritmo resolve 3-SAT mais rápido que cⁿ. Algoritmos engenhosos podem reduzir a base abaixo de 2, mas nunca até algo subexponencial. Formalmente: existe δ > 0 tal que 3-SAT não pode ser resolvido em tempo O(2^δn).

Por décadas, o progresso bateu com esse quadro. Pesquisadores foram aparando a base, mas ela permanecia bem acima de 1. Como 3-SAT pode ser convertido em muitos outros problemas, a ETH virou uma suposição de trabalho. Pesquisadores a usavam para argumentar que problemas como Clique, Vertex Cover, Conjunto Independente e outros também não podiam ser resolvidos muito mais rápido.

Como o novo resultado se compara

Esse novo limite é escrito como 2^o(n) em notação abreviada. O custo por variável adicionada se aproxima de 1 conforme n cresce, exatamente o que a ETH dizia ser impossível.

O que OpenAI e Anthropic anunciaram

Ambos os laboratórios chegaram essencialmente ao mesmo limite subexponencial de forma independente, e ambos sustentaram seus artigos com provas verificadas por máquina no assistente de provas Lean.

A Anthropic diz que o Claude encontrou o algoritmo central sem intervenção humana após produzir cerca de 14 milhões de tokens de saída. Seu método usa redes tensoriais e argumentos de posto (rank). Pesquisadores então ajudaram com a redação final.

Por que ambos os laboratórios encontraram no mesmo dia?

Nenhum dos laboratórios explicou o timing. O artigo da Anthropic chama os dois resultados de independentes e simultâneos, e os dois textos seguem caminhos diferentes na matemática para chegar essencialmente ao mesmo limite.

Algum contexto torna a coincidência menos surpreendente do que parece à primeira vista. Ambos os laboratórios têm direcionado seus modelos a longas listas de problemas em aberto, e só a OpenAI divulgou centenas de manuscritos de matemática gerados por IA no início de outubro. A ETH é um dos alvos mais conhecidos na área, e ambos os modelos aprenderam com a mesma pesquisa publicada. Descobertas independentes e simultâneas também são um padrão antigo na ciência, como com Newton e Leibniz no cálculo ou Darwin e Wallace na seleção natural.

Quão sólidas são as provas?

O Lean confirma que uma declaração formal decorre logicamente de seus axiomas. Ele não confirma que a declaração formal diga a mesma coisa que o artigo. A Anthropic observa que nenhuma máquina verifica essa correspondência, e a OpenAI diz que seu arquivo Lean prova um limite um pouco mais fraco do que o do título.

Agora, os mesmos pesquisadores que propuseram o problema, Impagliazzo e Paturi, junto com Ryan Williams, do MIT, estão organizando workshops para avaliar se as declarações formais realmente capturam a ETH. A carta deles enfatiza que participar da revisão não é um endosso. Até o momento da escrita deste artigo, ninguém havia apontado publicamente uma falha.

Williams disse que partes da prova da OpenAI parecem rotineiras, enquanto "duas ou três partes com cara de alienígena" ainda precisam de escrutínio. Impagliazzo, um dos autores da ETH, descreveu o resultado como profundamente surpreendente.

O que muda e o que não muda

Na prática, quase nada muda hoje (ufa): os novos algoritmos só superam a força bruta em entradas muito maiores do que qualquer computador poderia armazenar.

Nada de solvedores de SAT mais rápidos

O artigo da Anthropic diz que seu método só supera a força bruta em entradas astronomicamente grandes. Para fórmulas típicas com cinco cláusulas por variável, o ponto de cruzamento é um número com cerca de 10.000 dígitos. No caso mais geral, é um número com aproximadamente 100 milhões de dígitos.

Os autores também dizem que a abordagem deles dificilmente ajudará em algo com menos de cerca de 10 milhões de variáveis. Os solvedores de SAT usados em verificação de chips, escalonamento e planejamento não ficarão mais rápidos por causa deste resultado.

A criptografia não quebrou

O resultado não toca em P vs NP. Ninguém está afirmando isso. A OpenAI diz que testou se o algoritmo quebra cripto de verdade e está bastante confiante de que não.

A teoria será reescrita

O maior impacto é na pesquisa. Resultados de dureza baseados na ETH ou SETH agora precisam de um novo embasamento, e alguns pesquisadores disseram que anos de seus próprios trabalhos podem precisar ser revisitados. Nem tudo cai, porém. A Anthropic observa que o resultado não refuta o problema dos vetores ortogonais, que sustenta muitos resultados de complexidade de grão fino.

Por que isso importa para a IA

A manchete é menos sobre 3-SAT e mais sobre quem encontrou a resposta: dois sistemas de IA, de forma independente, derrubaram uma conjectura em que especialistas humanos confiavam há uma geração.

IA como colaboradora de pesquisa

Pesquisadores descrevem agora novos resultados de IA surgindo a cada semana ou duas, bagunçando projetos em andamento. Ferramentas formais como o Lean estão se tornando centrais porque permitem que humanos confiem em uma longa prova escrita por máquina sem refazer cada linha.

Atalhos ocultos e autoaperfeiçoamento

A ETH capturava a crença de que alguns problemas de busca não têm atalhos engenhosos. Se essa crença estiver errada, outros problemas obviamente difíceis podem esconder atalhos também.

Penso na descoberta de algoritmos como uma área em que esses atalhos podem importar muito para o autoaperfeiçoamento recursivo, que é a ideia de sistemas de IA que ajudam a projetar IAs melhores. Usar IA para encontrar algoritmos mais rápidos é um caminho concreto nessa direção, embora nada neste resultado faça isso diretamente hoje.

O que isso significa para quem trabalha com dados

Para quem constrói com dados, três lições se destacam:

• Teoria da complexidade não é só acadêmica: saber por que um problema é NP-difícil indica quando pensar em heurísticas, aproximações ou solvedores em vez de busca exata.
• Verificação é uma habilidade: conforme a IA gera mais código e análises, checar sua saída (com testes, provas ou pipelines reprodutíveis) importa tanto quanto produzi-la.
• Assintótica pode enganar: um algoritmo "mais rápido" na teoria pode ser inútil nos tamanhos do mundo real.

Conclusão

Se as provas resistirem à revisão de especialistas, a hipótese do tempo exponencial entra na lista curta de conjecturas amplamente aceitas que acabaram falsas (como a conjectura da soma de potências de Euler). Mas P vs NP continua em aberto e a criptografia está segura por enquanto.

Os próximos marcos a observar são os workshops de revisão liderados pelos autores originais da ETH, reimplementações independentes dos algoritmos e se alguém aperta ainda mais o limite.

Para construir as bases por trás de histórias como esta, explore nossos cursos de estruturas de dados e algoritmos, programação em Python e machine learning. Eles cobrem o pensamento de Big-O que torna resultados como este mais compreensíveis.