Hey guys!
So I've been wondering . . . Did anyone try to incorporate a SAT solver into their games? Or another Non-Polynomial time algorithm solver? From my knowledge of the universe, many problems involve non-polynomial time algorithms, and it may be rather limiting in some cases to restrict games to only handling P problems. As an example, the n-clique problem could be solved to find individual groups of friends within a virtual friend-sim game, or the graph-colouring problem could be solved to colour the procedurally-generated map of a game where the stylistic art restrictions demand only a few colours. These aren't the best of examples, but NP problems often crop up, and when they do, it's nice to be able to solve them efficiently.
It may be bothersome to solve these problems by hand each time they arise, especially if they're NP-complete. Instead, it's often possible to reduce an NP problem to something like SAT, and use a dedicated solver. I haven't done this, but it seems like an interesting way to approach the problem! I do admit that many games would not benefit from such a thing, but it might be an interesting idea to think about.
On an interesting note, it seems that many games (Sudoku, Go, Skyrim, etc.) create NP mini-problems for players to solve, perhaps masked under layers of game storyline and randomness. Most notable in typical video games is the Knapsack problem: given limited inventory space and items of different weight and value, which combination of items results in the greatest profit? I skimmed through this paper (https://arxiv.org/abs/1203.1895) which shows that many games are essentially NP challenges to the player, which is interesting to consider.
I guess one other application I can think of an NP-solver in video games is the availability of challenges for the player that go beyond NP. NP consists of problems that are difficult to solve, but easy to verify. Perhaps some games could offer problems that are difficult to solve, and difficult to verify, requiring an NP solver just to verify the winning condition. The usefulness of this is questionable, but might create a unique gameplay mechanic that would have been impossible before.