4 ms·
Amplifying on the other posts, just because a problem is an instance of a class that is NP-hard doesn't mean the specific problem is that hard. As mentioned els
by jerf 11y ago
Amplifying on the other posts, just because a problem is an instance of a class that is NP-hard doesn't mean the specific problem is that hard. As mentioned elsewhere in the conversation, subset sum is NP-complete [1], but, metaphorically, if Mario is capable of expressing the generalized subset sum problem, the human-played levels all amount to "Is there a submultiset of the numbers {1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1} that adds to 4?" Not only are all the levels completeable, they're basically trivially so, because what Mario game is there that involves solving sizable logic problems to progress? (Even the Ghost houses are just searches of a very small graph by computer science standards.)
[1]: https://en.wikipedia.org/wiki/Subset_sum_problem https://en.wikipedia.org/wiki/Subset_sum_problem