Laboratórios de IA de fronteira 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 monumentais que há muito intrigavam os pesquisadores. Um deles foi a rejeição surpreendente da Hipótese do Tempo Exponencial (ETH), uma suposição duradoura na ciência da computação que desempenha um papel importante em como entendemos o que é difícil de computar.
Assim como em divulgações de provas anteriores do laboratório de ponta, as comunidades científicas reagiram com uma mistura de entusiasmo e consternação. O matemático da Anthropic Levent Alpöge sugeriu que a OpenAI estava baseando suas soluções em trabalhos pré-existentes e, horas depois, a Anthropic 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 receberam o trabalho publicado 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á lançado.
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, já criticou a abordagem da OpenAI no passado, chamando sua divulgação de provas no início de outubro de um "ataque DDoS contra matemáticos".
No entanto, ele concordou em colaborar com os laboratórios de ponta para ajudar a direcionar ideias que são vitais para a área, disse ele ao TechCrunch. O laboratório pediu que ele ajudasse a interpretar a solução, juntamente com os cientistas da computação da UC San Diego Russell Impagliazzo e Ramamohan Paturi, que publicaram a ETH pela primeira vez em 1999.
O primeiro passo deles foi lançar uma carta aberta pedindo feedback de cientistas interessados nesses problemas e uma discussão sobre as normas em torno das contribuições de IA para o trabalho deles.
"Algumas partes [da prova da OpenAI] são, talvez você possa dizer, rotineiras, mas então sim, há duas ou três partes com aparência alienígena, e foram exatamente essas partes que vi e que me fizeram pensar: uau, isso é algo em que toda a comunidade precisa trabalhar junta", disse Williams ao TechCrunch.
A ETH faz parte de uma classe mais ampla de problemas conhecida como P vs NP, que tem animado a ciência da computação e muitas outras áreas por décadas. De forma redutiva, os pesquisadores estão tentando entender se qualquer problema cuja solução possa ser facilmente verificada (NP) também pode ser facilmente resolvido (P).
Um exemplo simples é o jogo Sudoku: uma vez que a solução de um quebra-cabeça está no lugar, ela pode ser rapidamente verificada, mas encontrar a solução consome muito tempo. Essa dinâmica é verdadeira em uma série de problemas importantes, e a percepção fundamenta os sistemas criptográficos: quando você tem a chave para uma mensagem codificada, você pode revelá-la, mas na verdade quebrar um código eficaz leva tempo demais para ser útil.
No entanto, os cientistas ainda precisam provar se isso é sempre verdade. "P = NP significa que, você não só pode verificar as soluções do Sudoku quando elas existem, como também pode simplesmente gerá-las", disse Williams. "P = NP está afirmando que isso é verdade para cada problema 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 para isso. Ela basicamente diz que até o algoritmo de computador mais rápido precisa de muito mais tempo exponencial para encontrar a solução à medida que o número de variáveis cresce em uma classe específica de quebra-cabeça lógico complexo.
As afirmações da OpenAI e da Anthropic são de que seus modelos criaram algoritmos que resolvem esses quebra-cabeças em tempo "subexponencial", o que significa mais rápido do que as velocidades consideradas possíveis anteriormente. Se for verdade, eles podem ter provado que a EFT é falsa — refutada, em termos científicos — e talvez aberto um caminho para algoritmos que geralmente realizam 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. "Eu acho que isso meio que coloca em questão muitas das intuições que pensávamos ter sobre... quão tratáveis são [os problemas difíceis de NP]. Também acho que esta provavelmente não é a resposta final também. Eu não acho que o algoritmo da OpenAI possa ser o melhor algoritmo que você pode obter."
A durabilidade da ETH fez com que ela fosse incluída em muitos artigos científicos na última década que precisarão ser revisitados se as alegações dos laboratórios de IA de que provaram que ela está errada se sustentarem, disse Williams.
"Isso é parte do motivo pelo qual eu estava pedindo ou pressionando a OpenAI para apoiar uma conferência sobre isso — isso vai afetar o trabalho de muitos pesquisadores, e precisamos descobrir, ok, o que acontece a seguir além de entender os algoritmos. Precisamos entender como as fundações devem mudar em comparação com o que tínhamos antes?", disse ele.
Antes das preocupações científicas, há questões de segurança cibernética. Williams disse que um algoritmo aprimorado pode implicar que os sistemas criptográficos que dependem de determinados tamanhos de chave podem ser considerados quebrados. Então, 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... algo está inseguro agora? E aparentemente, eles verificaram e estavam razoavelmente confiantes de que isso não... implicava em nenhuma quebra."
Esse novo paradigma de IA de descoberta científica ainda é um trabalho em andamento, mas Williams diz estar otimista 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 a adaptação mais fácil para ele do que para 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 realizam e a pensar mais profundamente sobre: ok, se todas as coisas em que eu costumava trabalhar agora são frutos fáceis para a IA, como posso elevar o nível para o tipo de perguntas científicas que quero fazer?"
