El ensayo cuestiona una creencia muy extendida en la informática: que los problemas NP-hard son intratables en la práctica. El autor recuerda cómo, al cerrar el curso, su profesora describió la disciplina como un proyecto acabado, dado que casi todos los problemas interesantes son indecidibles y, entre los decidibles, casi todos son NP-hard. Frente a esa visión, el texto sostiene que la teoría marca cotas superiores en el peor caso, pero no impide que existan algoritmos rápidos sobre el 99,9 % de las entradas, ni siquiera que aporten soluciones óptimas.
Para respaldarlo, repasa cinco problemas NP-hard clásicos. En resolución de dependencias de gestores de paquetes y en comprobación de tipos, el peor caso simplemente no aparece en el uso real. En planificación y en el problema del viajante, técnicamente problemas de optimización, existen herramientas comerciales y de código abierto, como Gurobi, SCIP o la suite de optimización de Google, capaces de devolver soluciones demostrablemente óptimas en tiempos razonables mediante mejores algoritmos, no mediante hardware exótico ni computación cuántica.
El artículo cita un trabajo que documenta una aceleración de 450.000 millones de veces entre 1991 y 2015 en problemas de selección de subconjuntos, atribuible más al progreso algorítmico que al del hardware. Incluso Boolean Satisfiability (SAT), el caso arquetípico de NP-hard, se resuelve hoy a escala industrial: Amazon publica que ejecuta alrededor de mil millones de consultas SMT al día, una variante aún más compleja de SAT, ya tratada como la parte sencilla del proceso. El autor cierra recomendando tratar los tiempos de espera patológicos como se trata un fallo HTTP: con un timeout y un mensaje de error, en lugar de asumir que el problema es irresoluble.