A OpenAI afirma que um modelo de IA refutou a Hipótese do Tempo Exponencial (ETH), desafiando uma suposição na qual pesquisadores confiaram por 27 anos. O modelo desenvolveu um algoritmo mais rápido para o problema lógico 3-SAT. O sistema da OpenAI gerou uma prova em linguagem natural em 16 de outubro. A equipe traduziu a prova para Lean no dia seguinte, permitindo que o software verificasse cada passo lógico.
O algoritmo publicado leva aproximadamente 2^(n/√log n) passos para uma entrada contendo n variáveis. Esse tempo de execução supera o limite inferior exponencial previsto pelo ETH, mas ainda é muito lento para aplicações práticas. A OpenAI alerta que são necessárias pesquisas substanciais adicionais para alcançar melhorias de velocidade práticas. Russell Impagliazzo e Ramamohan Paturi da UC San Diego liderarão a revisão junto com Ryan Williams do MIT. A OpenAI não está reivindicando crédito científico pela descoberta, seguindo uma disputa anterior envolvendo Navier-Stokes.
Impagliazzo e Paturi introduziram ETH em 1999. A hipótese refere-se ao 3-SAT, que pergunta se valores verdadeiro-ou-falso podem ser atribuídos a variáveis enquanto satisfazem cada condição ligada. Uma solução proposta é fácil de verificar, mas cada variável adicional duplica o número de combinações possíveis a serem pesquisadas. ETH afirma que nenhum algoritmo pode evitar o crescimento exponencial no pior caso. OpenAI diz que centenas de artigos usaram a hipótese para estabelecer dificuldade computacional em teoria dos grafos, biologia computacional e bancos de dados. O acrônimo ETH não tem conexão com o ticker do Ethereum.
O resultado não estabelece que P é igual a NP. A questão P versus NP pergunta se todos os problemas cujas soluções podem ser verificadas rapidamente também podem ser resolvidas rapidamente. O ETH fez uma afirmação mais forte do que P ≠ NP, portanto refutar o ETH não resolve essa questão mais ampla. O presidente e co-fundador da OpenAI, Greg Brockman, enfatizou essa distinção algumas horas após o anúncio. O algoritmo não ameaça diretamente a criptografia que protege o bitcoin ou o ethereum. As assinaturas do bitcoin usam criptografia de curva elíptica, e o algoritmo não resolve o problema matemático subjacente a esse sistema.
Scott Aaronson, professor de ciência da computação na Universidade do Texas em Austin, disse que estudantes lhe trouxeram a notícia da suposta refutação. Avanços matemáticos anteriores também refutaram suposições sobre limites computacionais. Anatoly Karatsuba refutou a conjectura de multiplicação de Andrey Kolmogorov em cerca de uma semana em 1960. Volker Strassen buscou estabelecer a otimalidade da multiplicação matricial padrão em 1969, mas acabou descobrindo uma abordagem mais rápida. Máquinas agora geram provas que os humanos depois trabalham para entender. O mesmo comunicado também afirmou provas adicionais envolvendo análise harmônica e física de partículas.
O criptógrafo Matthew Green alertou que a IA pode minar a matemática que protege as carteiras. Benjamin Cowen, membro do Conselho de Especialistas em Inteligência de Mercado da BeInCrypto, argumentou que desenvolvimentos em disciplinas distantes da finança podem, eventualmente, alterar mercados. Os avanços em IA cada vez mais testam as suposições de dificuldade computacional nas quais os ativos digitais dependem.