IA derruba hipótese chave da computação teórica após 27 anos

Computação

Modelos de IA desafiam conceito fundamental, exigindo revisão de pesquisas importantes na área.

Leia também: Escritório ligado a Musk cria entidade para difundir regras eleitorais duras nos EUA

A hipótese do tempo exponencial (ETH), base da ciência da computação teórica por 27 anos, acaba de ruir após provas geradas por sistemas de inteligência artificial de OpenAI e Anthropic, lançando no limbo décadas de pesquisas em complexidade computacional e design de algoritmos em universidades do mundo todo.

ETH sustentava que o esforço para resolver certos problemas cresce exponencialmente com o tamanho da entrada. Se as novas provas estiverem corretas, essa suposição está errada — e uma enorme quantidade de resultados passa a precisar de revisão ou deixa simplesmente de valer.

“ETH é falsa, metade do meu artigo não funciona”, resume o professor Peter Jonsson, da Universidade de Linköping, na Suécia. O trabalho que ele apresentaria em duas semanas em uma das conferências mais prestigiadas da área, o IEEE Symposium on Foundations of Computer Science, agora é exemplo de uma crise que ameaça boa parte do programa científico do evento.

Como a nova descoberta em IA tornou pesquisas anteriores irrelevantes?

A refutação de ETH pela IA atinge diretamente artigos que usavam a hipótese como base para demonstrar limites de algoritmos ou provar que determinados problemas exigem tempo exponencial. Sem ETH, as conclusões desses trabalhos perdem o chão.

Na prática, qualquer resultado do tipo “se ETH é verdadeira, então problema X não pode ser resolvido mais rápido que em tempo exponencial” vira suspeito. É o caso de dezenas de artigos de referência. Daniel Lokshtanov, professor da Universidade da Califórnia em Santa Barbara e um dos formuladores originais da hipótese, calcula que cerca de 50 de seus trabalhos científicos se tornam “sem sentido” ou terão de ser reescritos.

“É uma bomba gigante no meio do campo”, diz Lokshtanov. Ele próprio se descreve como “galacticamente errado” se o resultado da IA se confirmar. Já Thore Husfeldt, chefe do grupo de algoritmos da IT University of Copenhagen, afirma que o problema em que vinha trabalhando neste ano inteiro ficou irrelevante da noite para o dia.

“Como faróis iluminando um campo inteiro”, define Husfeldt. “É fantástico, como se alguém tivesse iluminado um campo inteiro com holofotes”, afirma, ao mesmo tempo em que passa dias reescrevendo cálculos no quadro negro para descobrir que partes do próprio trabalho se tornaram obsoletas.

Entenda o contexto

ETH foi proposta para capturar de forma precisa a intuição de que alguns problemas não admitem algoritmos significativamente mais rápidos do que os conhecidos. Em vez de provar impossibilidades absolutas, a hipótese servia como âncora: se ETH for verdadeira, então não existe algoritmo melhor do que tal limite para uma longa lista de problemas clássicos.

Esse tipo de suposição é comum em complexidade computacional, área que estuda quão difícil é resolver problemas em termos de tempo e recursos. Em 27 anos, ETH foi usada como base para desenhar algoritmos, argumentar sobre o que é ou não viável em grande escala e até orientar quais problemas valiam a pena ser atacados. Agora, pesquisadores como Jonsson falam em “trabalhos mortos” e em uma temporada de revisões maciças.

Quais avanços recentes em inteligência artificial estão revolucionando a ciência da computação?

O golpe em ETH vem de uma leva específica de avanços: modelos de IA capazes de produzir demonstrações matemáticas completas, tanto em linguagem natural quanto em formatos verificáveis por computador, como o sistema formal Lean.

Nesta semana, OpenAI e Anthropic divulgaram de forma coordenada provas que alegam refutar ETH. Os textos, com dezenas de páginas, foram publicados em repositórios abertos, acompanhados de versões formais em Lean que, em princípio, podem ser checadas automaticamente. O artigo principal da OpenAI sobre o tema tem cerca de 60 páginas.

Não é um movimento isolado. Neste mês, a OpenAI já havia despejado 722 manuscritos cobrindo 400 problemas de matemática e computação em um repositório público, movimento que irritou parte da comunidade acadêmica pela dificuldade de absorver o material e pelos erros encontrados em alguns textos.

A diferença agora, relatam pesquisadores, é que o trabalho sobre ETH parece bem mais consistente. Mesmo assim, ninguém teve tempo de verificar tudo. “Ler matemática é um grande investimento de tempo cognitivo”, lembra Husfeldt, que conta ter recebido um artigo de 17 páginas, aparentemente gerado por IA, sobre as consequências do novo resultado. Ele simplesmente decidiu não ler.

Como a prova foi gerada e quem está validando o resultado

As equipes de OpenAI e Anthropic treinaram modelos para propor argumentos matemáticos longos, passo a passo, e traduzir essas provas tanto para texto corrido quanto para a linguagem formal Lean. A promessa é que, uma vez checadas, essas demonstrações tenham o mesmo status de qualquer prova humana.

Ciente do impacto, a OpenAI acionou diretamente os criadores originais de ETH, incluindo cientistas da UC Santa Barbara, e um pesquisador do MIT que já havia refutado uma variante da hipótese, para liderar o esforço de validação. Há um formulário aberto convidando voluntários, além da promessa de financiar uma conferência dedicada ao tema.

Lokshtanov afirma que vai participar do mutirão para destrinchar as provas. Jonsson, em Linköping, planeja revisitar não só seus artigos, mas também trabalhos de colegas que dependiam de ETH. A expectativa é que, nas próximas semanas, o IEEE Symposium on Foundations of Computer Science se transforme em palco central para discutir o novo cenário.

Impacto psicológico e sobrecarga na academia

A revolução trazida pela IA não mexe apenas com fórmulas. Ela tem cobrado um preço emocional. “Os últimos meses têm sido difíceis, com resultados da IA que aniquilam projetos em andamento”, relata Husfeldt. Segundo ele, pesquisadores veem meses de trabalho desmoronarem a cada novo anúncio de máquina, o que tem levado departamentos a considerar até apoio psicológico especializado.

Além da sensação de estar sempre correndo atrás da tecnologia, há a questão da enxurrada de conteúdo. O pacote de 722 manuscritos da OpenAI é visto como exemplo de volume difícil de digerir, com trabalhos de qualidade desigual. Alguns acadêmicos acusam a empresa de agir com pressa para capitalizar comercialmente descobertas científicas, o que alimenta frustração e desconfiança.

O que muda na prática para a tecnologia e para a pesquisa

A curto prazo, o impacto é mais teórico do que prático: não há, de imediato, um novo algoritmo milagroso pronto para ser implementado em sistemas comerciais. Mas a derrubada de ETH reabre problemas considerados “intratáveis” e muda o mapa das fronteiras do que pode ou não ser computacionalmente eficiente.

Victor Lagerkvist, pesquisador em Linköping, diz que pretende revisitar questões que havia abandonado justamente por acreditar na validade de ETH. Se não é mais obrigatório que o tempo de resolução cresça exponencialmente, novas estratégias de algoritmos podem emergir, tornando possíveis aplicações hoje descartadas por custo computacional.

Na criptografia, a repercussão é mais indireta, mas preocupante. Muitos sistemas de segurança digital se apoiam na ideia de que certos problemas levam tempo impraticavelmente longo para serem resolvidos por qualquer algoritmo. “Embora esse resultado específico não atinja diretamente a criptografia, ele deveria definitivamente assustar alguns designers de criptossistemas”, avalia Lokshtanov.

Husfeldt resume o ponto: “Queremos que o processo científico aberto identifique nossos mal-entendidos sobre computação, em particular porque boa parte da infraestrutura digital moderna é construída sobre suposições sobre o que é ou não possível computar”.

IA como nova ferramenta de prova — e não como oráculo

Apesar do choque, há otimismo entre muitos teóricos. Para Jonsson, ter um veredito claro sobre ETH era algo que ele só “podia sonhar” até agora. A forma como esse veredito chegou importa menos do que sua correção. “Não me importo se é uma prova escrita por humano, por IA, ou se um alien a transmitiu para nós. Se for verdadeira, então devemos simplesmente usá-la no futuro”, afirma.

O episódio também consolida a IA como ferramenta metodológica disruptiva: em vez de apenas acelerar experimentos ou sugerir linhas de pesquisa, os modelos passam a produzir resultados centrais e altamente técnicos da matemática e da ciência da computação. O preço é a necessidade de desenvolver novos rituais de verificação, com humanos e máquinas trabalhando juntos.

Enquanto isso, pesquisadores correm para salvar o que podem de artigos baseados em ETH, apontar quais resultados ainda valem em um mundo sem a hipótese e, principalmente, explorar as novas portas que se abrem. Como define Husfeldt, é como se um campo inteiro tivesse sido subitamente iluminado — e agora todos precisam decidir para onde correr primeiro.