There's a long history of proving results like this. NP-Completeness is the norm, not the exception. Any system that's complex enough is almost surely NP-Compl

There's a long history of proving results like this. NP-Completeness is the norm, not the exception. Any system that's complex enough is almost surely NP-Complete. For similar reasons, Turing Machine Equivalence is also the norm, not the exception. These results are interesting but not unexpected. A more interesting question is under what conditions is the problem difficult to find solutions for. Many NP-Complete instance ensembles turn out to effectively have polynomial time solutions (3-SAT w/ uniform clause variable choice, Hamilton Cycles in Erdos-Renyi random graphs), so proving NP-Completeness is not a death knell for approximation.