Collecting Things Under Time Pressure is Hard.
Jayson Lynch · Tiny Trans. Comput. Sci. · 2012
We establish a scheme for showing the NP-Hardness of games with certain common mechanics including movement in three dimensions subject to gravity, ‘gathering’ items by co-locating with them, and having this collection process be subject to a time-limit. The Chinese Postman Problem (CPP) is the following: Given a mixed graph M = (V,E,A) with a cost function c defined on E ∪A, and an integer k, does there exist a route of cost k or less which traverses every edge and every arc at least once? We have not seen this problem used in the context of game complexity. Our method of reducing to the CPP, whose planar, mixed-graph variation is NP-Complete [2], allows the computational complexity of a large number of games to be proven NP-Hard. This includes Spyro 1 through 3, Guild Wars, and Grand Theft Auto 3. Further, the popular challenge of ‘speed-runs’ of games, where the player attempts to beat the game in the shortest time possible, be proven hard for many more games. Examples here include Mario 64, Super Mario Galaxy, and Mass Effect 1 through 3. This most directly builds on the work of Viglietta [3], who uses the method of reducing some common game mechanics to NP-Complete problems to prove a number of classic games hard, and Aloupis, Demaine, and Guo [1], whose recent work on Nintendo games gives a number of complexity results including NP and PSpace-Completeness, and suggests considering speed-runs of games as their own problem. BODY 3D games with gravity that require gathering objects to ensure traversing edges within a time-limit can be reduced from the NP-complete CPP.