Re:Pac-Man Proved NP-Hard
by argv_empty on Friday January 27, 2012 @08:38AM
(#3518188)
You've got this a little backwards. Being in NP means a correct solution can be checked by a deterministic TM in polynomial time. A problem is NP-hard if any problem in NP is polynomial time Turing reducible to it. NP-complete problems are those that are NP-hard and in NP (an NP-hard problem need not be NP-complete).
NP-Complete just means that a correct solution can be evaluated in polynomial time by a deterministic Turing machine. It says nothing of the number of solutions that exist.