Definition:NP Complexity Class

From ProofWiki
Jump to navigation Jump to search

Definition

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

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

or:

run forever

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


Example

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


Sources