Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: