El nuevo algoritmo de OpenAI para satisfacibilidad es exponencial en cualquier caso real

Efficient algorithms, the Exponential Time Hypothesis, and losing the plot

El autor repasa la historia de la definición de eficiencia en computación, desde Jack Edmonds hasta la teoría de la complejidad, y critica el reciente anuncio de OpenAI de un algoritmo subexponencial para el problema de satisfacibilidad. El algoritmo solo alcanza ese régimen para un número de variables inimaginablemente grande, mientras que para cualquier caso real ejecuta una búsqueda exhaustiva exponencial. La conclusión es que llevamos cincuenta años respondiendo la pregunta equivocada sobre qué significa ser eficiente.