Los problemas NP-difíciles no son tan intratables como crees
NP-Overrated
Aunque la teoría advierte que los problemas NP-difíciles son intratables en el peor caso, en la práctica suelen resolverse rápido. La resolución de dependencias, el chequeo de tipos, la programación de horarios y el problema del viajante se abordan con éxito usando mejores algoritmos y herramientas modernas. De hecho, un estudio cita una aceleración de 450 mil millones de veces entre 1991 y 2015. Incluso SAT, el arquetipo NP-difícil, se resuelve a escala masiva: Amazon maneja mil millones de consultas SMT al día.
En teoría, no hay diferencia entre teoría y práctica. Pero en la práctica, sí la hay.