I 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 poly

I 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.