Definition:NP Complexity Class
Jump to navigation
Jump to search
 | This article needs to be linked to other articles. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code. |
 | This page has been identified as a candidate for refactoring of basic complexity. In particular: extract example Until this has been finished, please leave {{Refactor}} in the code.
New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Refactor}} from the code. |
This page is about NP Complexity Class in the context of Computability Theory. For other uses, see Class.
Definition
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
or:
- run forever
where:
- $p$ is a polynomial
- $\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): '$..........$'