Classic Nintendo Games Are NP-Hard (2012)
jeremykun.com
jeremykun.com
I'm pretty sure this is inaccurate with respect to the actual mechanics of Super Mario Bros, although the technique needed might not work with the particular layout shown. As I recall, it's possible to build a bit of momentum and crouch into a one-block gap, then turn around and stand to have the collision push Mario through the gap. A similar technique combined with another quirk of the engine (it's possible to very briefly land on the seam between two blocks in a vertical wall) is used for the Minus World glitch.
The article is really only technically correct, as those are glitches and certainly not intended, but in actual practice, yeah, it's not totally correct.
In this gadget, there's no room to build up momentum.
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).
Proof: A decision problem H is NP-hard when for every problem L in NP, there is a polynomial-time reduction R from L to H.
By assumption, H has finitely many instances, so precalculate a binary lookup table T. Accessing a lookup table takes time polynomial in L's instance size, namely O(1).
The algorithm "T . R" is then a polynomial-time algorithm for H, so P = NP.
Usually this boils down to creating AND/OR gates using level tiles, and combining them together to form arbitrary computational problems. Usually 3-SAT, because it's straight forward to encode in logic gates.
The thing is, breaking bricks with Koopa shells was actually introduced in Super Mario Bros. 3. Before that, bricks could only be broken with big Mario.
I don't think it is a good definition of intelligence.
When the authors of this paper are saying that these games are NP-hard, they're taking some "poetic license": complexity classes are defined for problems that have instances of increasing sizes (as the complexity is defined as a function of the size). Super Mario is only one instance. So they analyze generalizations of the game, and as the game size grows to infinity it becomes very hard to play it.
For the real games, DL does pretty well (and even simpler agents do well).
(Not that I have the requisite knowledge to understand it).
Strictly speaking, NP isn’t so much about the finding of solutions, just the verification of their correctness. The finding part is P [edit: which is contained in NP].
P=NP would mean that if we can easily verify a solution , then we can also find it easily in the first place. P!=NP means that there are some problems which are easy to verify the solution for,but hard to find a solution for.
Because nitpicking is fun, I'll add my contribution and say that the traditional definition of NP is actually about the finding of solutions, and is the etymology of the phrase "non deterministic polynomial time". That is, a non deterministic machine (one that could magically search multiple states at once) can find a solution in polynomial time.
Of course, since our non deterministic algorithm could just be the enumerate all witnesses, and verify them, then the two definitions are equivalent, except for the verification-based one being much more intuitive.
Which is exactly what quantum computers can do for certain classes of problems, such as integer factorization.
Sadly, it seems not to be the case (or not yet found?) for the most well known and useful class of NP problems, NP-complete.
See this discussion https://news.ycombinator.com/item?id=1371150
It is widely believed that some problems in NP are not also in P, i.e. that the solutions cannot be found in polynomial time. Note that brute force may not be the most efficient way to solve such problems. For example, integer factorization is believed to not be in P, but the best known solution is much better than brute force.
NP Hard problems are problems that can be used to solve all other NP problems with only polynomial time overhead. For instance, you can "encode" any NP problem as a 3COLOR problem, and then solve the 3COLOR problem instead. The reason NP hardness is interesting is that if you could solve an NP hard problem in polynomial time, then all of NP can be solved in polynomial time, so P=NP.
Not all NP hard problems are actually in NP. In other words, there are some problems that can be used to solve any NP problem, but whose solutions cannot be verified in deterministic polynomial time. The problems in NP that are also NP hard are called NP complete problems; 3COLOR is an example of such a problem. If you can prove that a given NP complete problem cannot be solved in deterministic polynomial time, it means P!=NP.
> it's impossible to predict the best solution without brute forcing all possible combinations of action
That's not true; all possible combinations are not required to be checked; frequently a greedy algorithm can eliminate the majority of possibilities without actually checking them.
"Impossible" is also a very strong word.
Furthermore, there are plenty of problems where we currently can't solve them without bruteforce ("impossible" to do so), but we don't know if they're NP-complete/even in the NP-class.
However, the really important detail you're missing which makes your answer completely wrong is the verification of the proof.
If a problem is of NP Complexity, than it must be computationally easy to determine that an answer is correct in polynomial time.
Your answer simply stated that a solution could be found by brute-forcing, not that the answer is easy to verify once found, and not that said brute-forcing must not be in non-polynomial time.
By missing those two details, your answer is so far off the mark I'd recommend passing in an interview based on that alone.
What kind of work do you do that requires regular detailed analysis of the complexity class of algorithms?
It's been my experience that it's enough for an engineer to be able to say, "This algorithm will (not) run in an acceptable time for our expected input sizes," and that the precise definitions of NP complete and NP hard are best forgotten and looked up on Wikipedia when needed.
An example would be 3-SAT, which takes a boolean predicate of a particular form (that it is conjunctions of disjunctions of 3 variables), and then an assignment of the variables, and checks if it satisfies the predicate. You can do this in polynomial time, so 3-SAT is in NP.