News for hackers. Stuff that matters.
Re:Android Game "Push Down" shown to be NP-Complete by jganetsk on Monday May 03, 2010 @03:02PM (#1315719)
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.
Re:Android Game "Push Down" shown to be NP-Complete by iskander on Monday May 03, 2010 @03:19PM (#1315780)
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.