Re:Android Game "Push Down" shown to be NP-Complete
by Chirono on Monday May 03, 2010 @07:39PM
(#1316476)
Indeed. You're correct. But this does show NP-completeness.
A rather incredible theorem is the Cook-Levin theorem which states that any problem that can be verified in polynomial time can reduced to an instance of sat SAT (in polynomial time).
The practical upshot of this is that to show NP-completeness, you only need to provide a polynomial certificate and reduction to SAT, or some other know NP complete problem.
A rather incredible theorem is the Cook-Levin theorem which states that any problem that can be verified in polynomial time can reduced to an instance of sat SAT (in polynomial time).
The practical upshot of this is that to show NP-completeness, you only need to provide a polynomial certificate and reduction to SAT, or some other know NP complete problem.