I'm running an algorithms seminar and I'm trying to express the Hamiltonian cycle problem in a new way that is exciting to students. I know that many of them play a game called Hearthstone and I'm trying to express a problem in that game as a decision problem.
Essentially in most card games they break down and stop being fun when a mechanic, that the designer didn't anticipate, adds recursion. In Hearthstone and Yu-Gi-Oh! that problem is expressed well in this video. In the packet that I give them I explain how the mechanic works and how it leads to recursion, then I ask them the following:
Express the mechanic that leads to recursion in a card game formally with input and output states as a decision problem.
Show this problem is in NP by giving a verification algorithm for this problem and proving that algorithm is correct.
The Hamiltonian cycle problem is already known to be NP-complete. We can show that the recursion problem in card games is NP complete by reducing the Hamiltonian cycle problem to the card game recursion problem. Do so by first giving a reduction of Hamiltonian cycle problem to card game recursion problem. The reduction takes input to Hamiltonian cycle problem and converts it into input to the card game recursion problem. Then prove your reduction is correct.
My main question is: Did I state anything incorrectly and would you change anything about my formulation of the problem?