>Every decent puzzle game for instance is usually NP-hard.
An interesting question is how many of these puzzles are NP-hard in practice. For example, Minesweeper in NP-hard. However, it is possible to solve many games of Minesweeper using simple deductive reasoning in polynomial time. This leads to the question of what is the average difficulty of a random game. My best attempt at formalizing this question is to imagine reducing every game with a polynomial time algorithm, then look at the complexity of the remaining games. The complexity of an original game of size n could be the average after you reduce all games of size n with your polynomial time algorithm. If this new complexity is sub exponential than it feels as if there is some sense in which the game is not often NP-hard.
A more concrete example that comes to mind is Haskell's type inference. In general this type inference is NP-hard. However, there are algorithms that can solve it in polynomial time assuming a limit to nesting. Because no such limit actually exists, type inference is still exponential. But, because we never see arbitrarily deep nesting (except for contrived examples), this does not matter.
An interesting question is how many of these puzzles are NP-hard in practice. For example, Minesweeper in NP-hard. However, it is possible to solve many games of Minesweeper using simple deductive reasoning in polynomial time. This leads to the question of what is the average difficulty of a random game. My best attempt at formalizing this question is to imagine reducing every game with a polynomial time algorithm, then look at the complexity of the remaining games. The complexity of an original game of size n could be the average after you reduce all games of size n with your polynomial time algorithm. If this new complexity is sub exponential than it feels as if there is some sense in which the game is not often NP-hard.
A more concrete example that comes to mind is Haskell's type inference. In general this type inference is NP-hard. However, there are algorithms that can solve it in polynomial time assuming a limit to nesting. Because no such limit actually exists, type inference is still exponential. But, because we never see arbitrarily deep nesting (except for contrived examples), this does not matter.