alt Hacker News1. The study of complexity classes isn't intended to dissuade people from writing certain programs. It's intended to understand the nature and theoretical limits of computation. As far as practice goes, it can be used to show where heuristics are needed. Saying it's overrated is like saying calculus is overrated because most people don't need to use it every day. And BTW, many important problems are in classes believed to be way harder than NP (i.e. NP-complete is the easiest of the hard famous complexity classes). E.g., I've seen some people brag about some configuration language being easy to mechanically analyse because it's not Turing-complete, while in fact it's at least PSPACE-hard to analyse.
2. When there's some large set of instances of some NP-hard problem that are tractably solvable in practice (like SAT), the importance of that is that there's some non-NP-hard subset here. Indeed, SAT is FPT (fixed parameter tractable [1]), an "easier" type of NP, for which decomposition can help. In contrast, graph colouring is thought to not be FPT.
Replies
[dead]
> It's intended to understand the nature and theoretical limits of computation.
Not in a general sense, at least for standard complexity theory. It only deals with a very specific model of computation. Anyone with a sufficiently solid grasp of metamathematics intuitively understands that the distinction between solve and verify is nothing but a description of how badly matched our foundations are for the structure we're trying to view.
... This is the second time today I've posted about foundations like this.
> Saying it's overrated is like saying calculus is overrated because most people don't need to use it every day.
You should stop thinking by analogy.
The article was showing the difference between mathematicians and engineers. For the mathematicians that created Computation Science, the only interesting solutions are complete solutions to general questions, whereas for engineers it's perfectly acceptable to eliminate some corner cases, thereby solving a reduced and simplified version of the general problem.