OpenAI afirma refutar a Hipótese do Tempo Exponencial com novo algoritmo

ChainCatcher relata que a OpenAI anunciou recentemente que seu modelo de IA resolveu a hipótese do tempo exponencial, uma conjectura que persiste na ciência da computação há mais de vinte anos, cuja sigla em inglês é ETH — não se refere à Ethereum. A hipótese investiga o quão difícil são problemas particularmente complexos, usando o problema da satisfatibilidade booleana (SAT) como exemplo: dado um conjunto de condições lógicas, existe uma atribuição que torne todas as condições verdadeiras simultaneamente? À medida que o tamanho do problema aumenta, o melhor método conhecido basicamente consiste em testar todas as possíveis soluções uma a uma, com o custo temporal crescendo exponencialmente com o tamanho. A hipótese do tempo exponencial afirma ainda que tais problemas não podem ser acelerados significativamente e que não existem algoritmos eficientes de tempo subexponencial verdadeiramente viáveis. Desde sua proposta em 1999, essa hipótese tem sido um pilar fundamental da ciência da computação teórica, com inúmeros artigos baseando-se nela para provar que certos problemas são difíceis ou que certos algoritmos estão quase no limite ótimo. Se a hipótese do tempo exponencial for refutada, isso significaria que muitos problemas considerados quase impossíveis de acelerar poderiam, teoricamente, ter soluções melhores. A OpenAI afirma ter descoberto um algoritmo determinístico capaz de contar com precisão o número de soluções para o problema k-SAT em tempo subexponencial, e validou formalmente o resultado usando Lean. Se esse resultado resistir à revisão por especialistas, abalará diretamente a hipótese do tempo exponencial.