This is kind of why P vs NP is such an interesting problem. It seems that a big family of NP-hard problems in fact _can_ be solved efficiently if we allow relaxing some constraints, like optimality (eg TSP), or generality of our algorithm (eg type checking).

I feel that is similar to how adding randomness to cryptography [1] opened a bunch of new systems like zero knowledge proofs[2]. By allowing us to be wrong in a very small number of instances (arbitrarily small by adjusting things like key size), we can build practical systems with really impressive properties.

[1]: Goldwasser and Micali - Probabilistic Encryption, 1983 https://web.archive.org/web/20090319000035/http://groups.csa... [2]: Goldwasser, Micali and Rackoff - The knowledge complexity of interactive proof-systems, 1985 https://courses.csail.mit.edu/6.857/2008/handouts/1989-siamj...