Definition:NP Complexity Class

From ProofWiki
Jump to navigation Jump to search

This page is about NP Complexity Class in the context of Computability Theory. For other uses, see Class.


In computability theory, $NP$ is a complexity class in which there exists some nondeterministic Turing machine that will either:

halt within $\map p {\size x}$ steps


run forever


$p$ is a polynomial
$\size x$ is the length of the input to the Machine.


Boolean Satisfiability is $NP$ because a nondeterministic Turing machine can pick values for all the variables and determine within $\map O {\size x}$ steps if the values are a solution to the problem.

If they are then the machine stops.

Otherwise it loops forever.

Also see