NP

From Wikipedia

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

In complexity theory, NP is the set of decision problems solvable in polynomial time on a nondeterministic Turing machine. Or, equivalently, YES answers are checkable in polynomial time on a deterministic Turing machine. See Complexity classes P and NP and NP-Complete.