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

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?".