> Most of the NP-Complete problems can be solved in polynomial time (but not all, of course!) with appropriate heuristics. We need to be careful when distingui

> Most of the NP-Complete problems can be solved in polynomial time (but not all, of course!) with appropriate heuristics. We need to be careful when distinguishing a "problem" (e.g. SAT) and an "instance of a problem" (e.g. "is this formula satisfiable?"). Heuristics can often help us solve real-world problem instances (e.g. seat planning for this wedding; a Hamiltonian path for this salesman; etc.), at least approximately/close-enough-to-be-useful. However, we must give resource bounds to such implementations (e.g. a timeout), since there's no way to know/check if a given instance will have worst-case behaviour until we run it. What I find fascinating is that we can prove that some problems are just as hard to solve approximately as they are to solve optimally! https://en.wikipedia.org/wiki/Hardness_of_approximation https://en.wikipedia.org/wiki/Hardness_of_approximation