Wow, I never guessed that my simple proof achieved so much resonance! You're right in the comments that the proof just shows the NP-hardness. I ommitted the ot

Wow, I never guessed that my simple proof achieved so much resonance! You're right in the comments that the proof just shows the NP-hardness. I ommitted the other part of the proof, because it seemed obvious to me - as others already said, you just have to find a solution of the level by nondeterministically "guessing" and verifying it. Of course, the game levels can get arbitrarily large. You have to assume this for any problem, otherwise there is only a finite (and therefore constant) number of configurations of the problem, and checking them can be done in constant time. Btw., I also found a direct reduction from directed Hamiltonian cycle. The proof is a little bit more complicated, the idea is that you have to collect a key in each node, and that you can leave each node only once, i.e., leaving a node on one edge will block all other outgoing edges of the node. Another technical difficulty was to create crossing edges. If you are interested in the proof, I'll ask Holger to put the example level in his blog.