5 ms·
This seems strange to me. Mario doesn't "feel" NP-hard. I guess I'll have to read the paper tonight.
by echelon 11y ago
This seems strange to me. Mario doesn't "feel" NP-hard. I guess I'll have to read the paper tonight.
- theseatoms 11y agoAnd/or play some video games.
- canjobear 11y agoPlaying the game isn't NP-hard, rather the task of deciding whether a level can be completed or not is NP hard (in fact, NP-complete for Super Mario Bros. and PSPACE-complete for Zelda games).
- xigency 11y agoBeing able to complete a level requires knowing that the level can be completed.