Os laboratórios Frontier AI dizem que seus modelos refutaram a hipótese do tempo exponencial. O que isso significa?

A OpenAI lançou ontem soluções para três problemas matemáticos de grande sucesso que há muito incomodam os pesquisadores. Uma delas foi uma rejeição surpresa da Hipótese do Tempo Exponencial (ETH), uma suposição durável na ciência da computação que desempenha um papel importante na forma como entendemos o que é difícil de calcular.

Tal como aconteceu com as provas anteriores do laboratório de fronteira, as comunidades científicas responderam com uma mistura de emoção e consternação. O matemático antrópico Levent Alpöge sugeriu que a OpenAI estava baseando suas soluções em trabalhos pré-existentes e, horas depois, a Anthropic posteriormente lançou sua própria refutação da ETH.

No entanto, o processo da OpenAI está evoluindo. Desta vez, o laboratório estruturou seus lançamentos de forma diferente para cada uma das três disciplinas envolvidas: os matemáticos colocaram o trabalho no GitHub; os cientistas da computação formaram um grupo de trabalho, pediram que as provas fossem compartilhadas publicamente e que a OpenAI financiasse uma conferência para discuti-las; os físicos formaram um grupo de trabalho que determinará como seu resultado será divulgado.

O professor do MIT, Ryan Williams, é o cientista da computação que está organizando a resposta de sua área à nova descoberta. Williams, cujo trabalho se concentra nessas questões de complexidade computacional, criticou a abordagem da OpenAI no passado, chamando seu despejo de provas no início de outubro de “ataque DDOS contra matemáticos”.

No entanto, ele concordou em colaborar com os laboratórios de fronteira para ajudar a orientar ideias que são vitais para a área, disse ele ao TechCrunch. O laboratório pediu-lhe que ajudasse a interpretar a solução, juntamente com os cientistas da computação da UC San Diego, Russell Impagliazzo e Ramamohan Paturi, que publicaram o ETH pela primeira vez em 1999.

O primeiro passo foi publicar uma carta aberta pedindo feedback de cientistas interessados ​​nestes problemas e uma discussão sobre as normas em torno das contribuições da IA ​​para o seu trabalho.

“Algumas partes (da prova da OpenAI) são, talvez você possa dizer, rotineiras, mas sim, há duas ou três partes que parecem alienígenas, e foram exatamente essas partes que vi que me fizeram pensar, uau, isso é algo que toda a comunidade precisa trabalhar em conjunto”, disse Williams ao TechCrunch.

Você concorda com P vs NP?

O ETH faz parte de uma classe mais ampla de problemas conhecida como P vs NP, que animou a ciência da computação e muitos outros campos por décadas. Redutivamente, os pesquisadores estão tentando entender se algum problema cuja solução pode ser facilmente verificada (NP) também pode ser facilmente resolvido (P).

Um exemplo simples é o jogo Sodoku: uma vez encontrada uma solução para um quebra-cabeça, ela pode ser verificada rapidamente, mas encontrar a solução é demorado. Essa dinâmica é verdadeira em uma série de problemas importantes, e o insight sustenta os sistemas criptográficos: quando você tem a chave para uma mensagem codificada, você pode revelá-la, mas decifrar um código eficaz leva muito tempo para ser útil.

No entanto, os cientistas ainda não provaram se isso é sempre verdade. “P = NP está dizendo que você não só pode verificar soluções de Sudoku quando elas existem, mas também gerá-las”, disse Williams. “P = NP está afirmando que isso é verdade para todos os problemas que você pode verificar rapidamente – se você pode verificá-lo rapidamente, você pode resolvê-lo rapidamente. Então, isso parece bom demais para ser verdade.”

É por isso que a maioria dos cientistas assume que P ≠ NP. A ETH forneceu evidências disso. Basicamente, diz que mesmo o algoritmo de computador mais rápido precisa de exponencialmente mais tempo para encontrar uma solução à medida que o número de variáveis ​​aumenta em uma classe específica de quebra-cabeça lógico complicado.

As afirmações da OpenAI e da Anthropic é que seus modelos criaram algoritmos que resolvem esses quebra-cabeças em tempo “subexponencial”, ou seja, mais rápido do que as velocidades anteriormente consideradas possíveis. Se for verdade, eles podem ter provado que a EFT é falsa – refutando-a, em termos científicos – e talvez abrindo caminho para algoritmos que geralmente executam P = NP.

“Todo cientista da computação provavelmente deveria dar um pouco mais de peso à plausibilidade de P = NP, mas o peso de cada um pode variar”, disse Williams. “Acho que isso questiona muitas das intuições que pensávamos ter sobre… quão tratáveis ​​(problemas NP difíceis) são. Também acho que essa provavelmente também não é a resposta final. Não acho que o algoritmo da OpenAI possa ser o melhor algoritmo que você pode obter.”

O trabalho futuro para cientistas da computação

A durabilidade da ETH fez com que ela fosse incluída em muitos artigos científicos na última década, que precisarão ser revisados ​​se os laboratórios de IA afirmarem que provaram que ela estava errada, disse Williams.

“Em parte, é por isso que eu estava pedindo ou pressionando a OpenAI para apoiar uma conferência sobre isso – isso afetará o trabalho de muitos pesquisadores, e precisamos descobrir, ok, o que acontece a seguir, além de entender os algoritmos, precisamos entender quais deveriam ser os fundamentos que tínhamos antes?” ele disse.

Antes das preocupações científicas, existem questões de segurança cibernética. Williams disse que um algoritmo melhorado poderia implicar que sistemas criptográficos que dependem de certos tamanhos de chave poderiam ser considerados quebrados. Portanto, uma das primeiras perguntas que ele fez ao líder científico da OpenAI, Dan Roberts, “foi se eles haviam verificado se isso afeta algum sistema criptográfico… há algo inseguro agora? E, aparentemente, eles verificaram e estavam razoavelmente confiantes de que isso não… implicava qualquer quebra”.

Este novo paradigma de descoberta científica da IA ​​ainda é um trabalho em progresso, mas Williams diz que está optimista, apesar das preocupações reais, particularmente sobre a formação da próxima geração de cientistas. Ser um cientista da computação que faz matemática de alto nível talvez tenha tornado o ajuste mais fácil para ele do que para os matemáticos puros.

Ainda assim, ele diz que a IA está “forçando as pessoas a serem um pouco mais ambiciosas sobre o tipo de trabalho que fazem, e a pensarem mais profundamente sobre tudo bem, se todas as coisas em que eu costumava trabalhar são agora frutos fáceis de alcançar para a IA, como posso elevar a fasquia para o tipo de questões científicas que quero fazer?”