Most instances of a class of problems that are NP-hard are in fact easy. Usually NP-hard is something resembling exponential blow-up in a problematic edge case.
One of my favorite terms in this space is 'relaxation'.
When you set yourself against the worst case scenario, you are destined to have a very bad time. But there are subsets of the problem where one or two details are treated as trivialities, while still keeping the rest of the problem 'interesting' or 'useful'.
Compression cannot compress white noise. But it turns out humans don't find noise that interesting (except in the negative). We value signal, and meaning. Most of the communication we care to exchange has a much more straightforward message than the medium, and so we continue to find new ways to condense both the message, and the most valuable nuance, down.
When you set yourself against the worst case scenario, you are destined to have a very bad time. But there are subsets of the problem where one or two details are treated as trivialities, while still keeping the rest of the problem 'interesting' or 'useful'.
Compression cannot compress white noise. But it turns out humans don't find noise that interesting (except in the negative). We value signal, and meaning. Most of the communication we care to exchange has a much more straightforward message than the medium, and so we continue to find new ways to condense both the message, and the most valuable nuance, down.