4 ms·
Do they show that the games are NP hard, or that it is possible to construct puzzles using the rules of the games that are NP hard?
by tinco 9y ago
Do they show that the games are NP hard, or that it is possible to construct puzzles using the rules of the games that are NP hard?
- icen 9y agoThe games themselves are fixed size. They can't be NP-hard, since NP-hardness is a property of difficulty with respect to input size. They show that you can generalise them and build levels that are NP-hard: for example, in the case of Pokemon, they build systems requiring that the player have a specific team (one that is very unlikely to ever actually be used).