OpenAI afirma desmentir la hipótesis del tiempo exponencial con un nuevo algoritmo

ChainCatcher informa que OpenAI anunció recientemente que su modelo de IA resolvió la hipótesis de tiempo exponencial, una conjetura en ciencias de la computación que ha prevalecido durante más de veinte años, cuya abreviatura en inglés es ETH, y no se refiere a Ethereum. Esta hipótesis se centra en cuán difíciles son ciertos problemas extremadamente complejos, utilizando el problema de satisfacibilidad booleana (SAT) como ejemplo: dado un conjunto de condiciones lógicas, ¿existe una asignación que haga que todas las condiciones se cumplan simultáneamente? A medida que aumenta la escala del problema, el mejor método conocido consiste básicamente en probar cada posible respuesta uno por uno, con un costo temporal que crece exponencialmente con la escala. La hipótesis de tiempo exponencial afirma además que estos problemas no pueden acelerarse significativamente en esencia, y que no existen algoritmos eficientes de tiempo subexponencial verdaderamente viables. Desde su propuesta en 1999, esta hipótesis ha sido un pilar fundamental en la ciencia teórica de la computación, con numerosos artículos basándose en ella para demostrar que ciertos problemas son difíciles o que ciertos algoritmos ya están cerca de ser óptimos. Si se refutara la hipótesis de tiempo exponencial, significaría que muchos problemas considerados casi imposibles de acelerar podrían teóricamente tener soluciones mejores. OpenAI afirma que su modelo encontró un algoritmo determinista capaz de contar con precisión el número de soluciones del problema k-SAT en tiempo subexponencial, y lo verificó formalmente mediante Lean. Si este resultado finalmente supera el examen de expertos, socavará directamente la hipótesis de tiempo exponencial.