| Herb Simon noted the optimal solution is often infeasible a long time ago. He argued that economic agents rarely finding a satisfying solution to their constraints, and instead choose a "satisficing" or "good-enough" solution. Simon also noted that the satisficing solution found by humans is often close to the optimal solution. He got (and deserved) a Nobel prize for these two observations. I find work of the flavor "X reduces to P = NP, so Nyah!" to be deeply unsatisfying and misleading. For problems of human importance, good-enough solutions to NP problems can often be found in a reasonable amount of time. In fact, state-of-the-art SAT solvers are mind-bogglingly fast (on average). They can find solutions in seconds, where the theoretical worst case solution time is many-fold the expected lifetime of the universe. Generating a hard instance of SAT is actually hard to do. One of the few reliable techniques we know of is to encode prime factorization into a circuit. This is good news for crypto, but bad news for anyone looking to show the real-world intractability of a process by reducing it to P=NP. Few processes in nature actually mimic prime factorization or graph isomorphism. |
It only become deeply unsatisfying and misleading for people who do not understand how to translate this information to the real world.
It seems from your post as you do have that understanding, but not the respect for the importance of the underlying math.