Classic Nintendo Games Are NP-Hard (2012)

I wondered how this could possibly work, then found this sentence. Basically their generalisations have to go far beyond what these games are (the NES mario games had everything be forgotten when you scrolled along).<p>&gt; For example, recall that in Super Mario Bros. everything substantially off screen resets to its initial state. Thus, if we generalize the stage size in Super Mario Bros. but keep the screen size constant, then reachability of the goal can be decided in polynomial time:

Interesting - I wonder if NP-hardness can be used as a sufficient indicator of how &quot;enjoyably challenging&quot; a game is. There&#x27;s a reason these games are such classics, and I dont think its entirely because of their timing, polish, and marketing. Miyamoto&#x27;s games always had that special &quot;something&quot; (opinion, I know), maybe this has something to do with it?

Can someone explain what is NP-Hard in a few sentences?

This is my algorithms professor :D Dope!

This seems strange to me. Mario doesn&#x27;t &quot;feel&quot; NP-hard. I guess I&#x27;ll have to read the paper tonight.

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]?<p>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?<p>[1]: <a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=xOCurBYI_gY" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=xOCurBYI_gY</a>

Why is this even a surprise, people have been participating in AI challenges for long time (like these : <a href="http:&#x2F;&#x2F;ants.aichallenge.org&#x2F;" rel="nofollow">http:&#x2F;&#x2F;ants.aichallenge.org&#x2F;</a> ) and are well aware that those are hard problems, they develop heuristics since its not computationally possible to obtain perfect solution.

big NES fan here, not a low level programmer - can someone ELI5?

Let&#x27;s make quantum computers play Nintendo games then.

I figured that out when I was 3.

What is that even supposed to mean? The abstract doesn&#x27;t clarify what &quot;NP-hardness&quot; means in terms of video games.<p>This looks really click-baity.<p>In terms of writing a Nintendo game, the solution is a fixed constant: the game&#x27;s binary.<p>In terms of solving a Nintendo game, (playing to completion), the solution is in constant time: the amount of time it takes to play the game.<p>Edit: Great, downvotes.