4 ms·

So as someone with only a lay understanding of what NP-Hard means - does anyone remember that neural network that someone trained to play the game[1]? So if yo

So as someone with only a lay understanding of what NP-Hard means - does anyone remember that neural network that someone trained to play the game[1]? So if you can train a neural network to solve an NP-Hard problem, does that mean by definition (since NP refers to a whole class of problems) that a neural network could eventually be trained to solve any given NPH problem given the time and compute resources to do so? [1]: https://www.youtube.com/watch?v=xOCurBYI_gY https://www.youtube.com/watch?v=xOCurBYI_gY

gohrt 11y ago
The actual games are not NP-hard problem generators. The rules of games can be generalized to create NP-hard problems.
yoavz 11y ago
If a problem is NP-Hard, it does not mean it cannot be solved. Rather, it means it cannot be solved efficiently (in polynomial time). Most NPH problems, now including Mario and 3SAT, can be solved given the time and compute resources to do so.
- lorenzhs 11y ago
  Well, to be exact, it's an open question whether they can be solved efficiently or not. The general assumption is that they can't, but it hasn't been proven yet.
runholm 11y ago
A neural network does not give any guarantee of solving the problem within any number of iteration. NP-hard problems can be solved, but the solution take a lot of time to find and a slightly larger problem is even harder to solve. Neural networks is an AI method of searching the solution space in a more intelligent way than "trying everything" (true for most AI methods actually).
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

gohrt 11y ago

The actual games are not NP-hard problem generators. The rules of games can be generalized to create NP-hard problems.

yoavz 11y ago

If a problem is NP-Hard, it does not mean it cannot be solved. Rather, it means it cannot be solved efficiently (in polynomial time). Most NPH problems, now including Mario and 3SAT, can be solved given the time and compute resources to do so.

lorenzhs 11y ago
Well, to be exact, it's an open question whether they can be solved efficiently or not. The general assumption is that they can't, but it hasn't been proven yet.

runholm 11y ago

A neural network does not give any guarantee of solving the problem within any number of iteration. NP-hard problems can be solved, but the solution take a lot of time to find and a slightly larger problem is even harder to solve. Neural networks is an AI method of searching the solution space in a more intelligent way than "trying everything" (true for most AI methods actually).

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