> I think NP-Completeness is the norm rather than the exception.
I don't think that's possible. Being NP-complete means a problem is as hard as any NP problem, and no harder. But there's not an upper limit to how difficult a problem can be.
Note that the problem of determining whether two different regular expressions match the same set of strings is much harder than any NP-complete problem.
When you think about the class of things that humans consider to be "fun logic puzzles", NP-Completeness seems more common, since it encapsulates broadly the set of puzzles that require a certain amount of brute-force to find a solution to, and any reasonably entertaining human-solvable puzzle is easy to verify that something is in fact a solution.
I think that's an unkind reading of my response. I was implicitly talking about decision problems or puzzle problems like the one in the OP.
If you're talking about PSPACE complete problems or general Turing machine equivalence, I would extend the statement to include those as well. That is, PSPACE-completeness or general Turing machine equivalence are the norm rather than the exception.
I'll also point out that a slight rephrasing of the question makes a statement about general computation into an NP-Complete problem. For example, instead of "Does this TM halt?" to "Is there some input for which this TM halts with finite tape length N in at most K steps?".
[0] https://en.wikipedia.org/wiki/List_of_NP-complete_problems#G...