# Definition:NP Complexity Class

Jump to navigation
Jump to search

## Contents

## 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

- NP Problem iff Solution Verifiable in Polynomial Time: applied during investigations into whether a potential solution to a problem can be verified on a deterministic Turing Machine in polynomial time.

- Hence Definition:P Complexity Class: a subclass of $NP$.

## Sources

- 1986: David Wells:
*Curious and Interesting Numbers*... (previous) ... (next): '$..........$' - 1997: David Wells:
*Curious and Interesting Numbers*(2nd ed.) ... (previous) ... (next): '$..........$'