"In our implementations, we use three kinds of objects. Walls, represented by dark grey blocks, cannot be occupied or walked through. Trainers' lines of sight are indicated by translucent rectangles. We have two types of Trainers. Weak Trainers, represented by red rectangles, are Trainers whom the player can defeat with certainty without expending any effort, i.e., without consuming PP or taking damage. Strong Trainers, represented by blue rectangles, are Trainers against whom the player will always lose.
"We can implement weak and strong Trainers as follows (a construction due to Istvan Chung). Weak Trainers each hold a Level 100 Electrode with maximum Speed and equipped with only the Self Destruct move. Strong Trainers each hold two Snorlaxes, with Speed of 30. The player has no items, and only one Pokemon in his team. For Generation I and II games (Red/Blue/Yellow and Gold/Silver/Crystal versions respectively), the player holds a Gastly which has learned Self Destruct using TM36, and its PP for its other moves have all been expended, so it can only use Self Destruct in battle. When the player encounters a weak Trainer, the enemy Electrode will move first and use Self Destruct, which deals no damage to Gastly because Self Destruct is a Normal type attack and Gastly is Ghost type, so the weak Trainer immediately loses. When the player encounters a strong Trainer, Gastly moves first and uses Self Destruct, causing the player to lose (even if it defeats the enemy Snorlax, the opponent holds another one). This implementation only works in Generations I and II because TM36 exists only in Generation I and the Time Capsule feature in Generation II allows a Gastly with Self Destruct to be traded from Generation I to Generation II. In Generations III, IV, and V, Gastly can be replaced by Duskull, which is allowed to learn the move Memento, which serves the same purpose as Self Destruct, via breeding."
https://arxiv.org/pdf/1203.1895.pdf
Fascinating stuff.
Pokemon has been NP-complete since they were able to use save data corruption to freely rewrite the game's ROM.
Bump because this is some interesting stuff. You sadly posted it at a bad timing where SM stuff is running rampant.
>>26571850
Seems so...
>>26570918
I read this up on wikipedia, and still have no idea what it means. Guess I'm retarded.
I read through the Pokémon section and tried to make sense of it.
So basically they are trying to set up some artificial situations that conform to a set of rules they previously set up, which can be used to prove NP-completeness (I still don't fully understand what that is).
>Situation 1 (Figure 33)
>When coming from path a, you must choose either b or c exclusively. Choosing one path locks the other.
>Situation 2 (Figure 34)
>As long as you haven't talked to all of the weak trainers from above, you can pass.
>Situation 3 (Figure 35)
>Pretty self-explanatory. If you walk from a to b, the trainer will move in such a way as to make it impossible to walk from b to a or from a to b again.
>Situation 4 (Figure 36)
>If you enter from x, you can only exit through x'. If you enter through y, you can only exit from y'.
Why does the ability to construct these situations prove NP-completeness? I have no idea, but it'd be cool if someone could chime in.
As far as I know, an NP-Complete problem is one that demands every possible outcome to be analysed in orther to be solved.
A "P" (polynomial) problem, on the other hand, can have a general solution.
For example, supose you have a backpack where you can store items with specific values and you want to maximize the total value inside the backpack:
If fractions of items are allowed, you can just choose always the most expensive until it fills up. This is polynomial.
If fractions are not allowed, there is no easy way to tell what is the best choice. The best item could ocupy 60% of it, and every other just 50%, but it might be better to take two of another item than one of the most valuable. You have to check every combination, there is no polynomial algorithm. Hence, NP, non-polynomial.
>>26575570
>Hence, NP, non-polynomial.
NP means nondeterministic polynomial time, not non-polynomial. That doesn't even make sense.
I dont understand what's being said here, someone explain? It sounds interesting but I can't make heads or tails of it.
>>26576030
To prove that Pokémon games are NP-complete, they show that you can use game rules to construct a scenario that has been proven to be NP-complete in prior work. They construct this scenario by using trainer battles.
>In computational complexity theory, a decision problem is >NP-complete when it is both in NP and NP-hard. The set of >NP-complete problems is often denoted by NP-C or NPC. The >abbreviation NP refers to "nondeterministic polynomial time".
>Although any given solution to an NP-complete problem can be verified >quickly (in polynomial time), there is no known efficient way to locate a >solution in the first place; indeed, the most notable characteristic of >NP-complete problems is that no fast solution to them is known.
>>26576104
what the fuck is "NP complete"?
>>26576030
It's not interesting and it doesn't mean anything.
They basically asked the question
>Can you make a romhack where players are railoaded to a specific position in the most autistic way possible
And the answer is, surprisingly, yes, with this "paper" revolutionizing abstract mathematics and computer science
>>26576693
If you don't know what NP-completeness is, you probably shouldn't be here unless you want to learn a lot of new stuff on math and cs
https://en.wikipedia.org/wiki/NP-completeness
>>26571008
That's Turing-completeness. NP-Complete is about complexity.
