3 ms·
The key word in the original paper (from 2012 (!)) is "Generalized". IIRC, it's trivial that to "solve" Zelda Polynomial time (with an emulator) -- the entire
by cbhl 14y ago
The key word in the original paper (from 2012 (!)) is "Generalized".
IIRC, it's trivial that to "solve" Zelda Polynomial time (with an emulator) -- the entire state space of the console can be represented in constant space, so a trivial algorithm would be to traverse the state space tree with breadth-first search.
- Dylan16807 14y agoPicking a 'constant' of 2^k, with k the entire memory space of the console, is a rather inaccurate representation. It's like arguing that a desktop computer is not turing complete: true in such a narrow sense that using it to win a bar bet is going to lead to someone getting punched in the face.