People like games that are NP-complete

Recently, I've been thinking about the types of games that people like to play most on their phones and at parties. Games that are NP-complete seem to strike the right balance - they're challenging, but don't take too much practice. Polynomial time games (like Tic Tac Toe and Connect Four) feel too easy and exponential time games (like chess and go) have steep learning curves.

In NP-complete games, you can quickly verify whether a move is valid, but it is hard to decide what you'll do on your turn.

Here are some examples:

Seems like it may be worth going through Karp's 21 NP-Complete Problems to brainstorm some new games.