4 ms·
Based on the description in this blog post, this proof shows that the game is NP-hard. They have not indicated that they proved that it was NP-complete.
by jganetsk 16y ago
Based on the description in this blog post, this proof shows that the game is NP-hard. They have not indicated that they proved that it was NP-complete.
- iskander 16y agoI haven't played this game but it looks like the certificate is just the solved level-- verifying that a cleared path exists can definitely be done in time polynomial with the level size.