News for hackers. Stuff that matters.
Re:Classic Nintendo Games Are NP-Hard (2012) by icen on Thursday December 28, 2017 @11:01AM (#16022743)
A problem is in NP if a Turing machine, given the problem, can verify a given solution (assuming that the size of the solution is polynomial in the size of the problem) in a number of steps polynomial in the size of the problem.

An example would be 3-SAT, which takes a boolean predicate of a particular form (that it is conjunctions of disjunctions of 3 variables), and then an assignment of the variables, and checks if it satisfies the predicate. You can do this in polynomial time, so 3-SAT is in NP.

There are no comments on this comment yet.