# Nondeterministic Polynomial Time **A class of algorithm [[Time Complexity|running time]] upper bounded by a polynomial of the input size on a non-deterministic [[Turing machine]].** > [!Example] Nondeterministic Polynomial Time > An algorithm is of **nondeterministic polynomial time** if its time complexity can be [[Big O Notation#Big O|upper bounded]] by a polynomial expression of the input size on a *nondeterministic* Turning machine. That is, > $T(n)=O(n^k)$ > for some positive *constant* $k$. A decision problem that can be solved in polynomial time on a nondeterministic Turning machine belongs to the *complexity class NP*. > [!Example] NP Complexity Class > A decision problem $A(x)$ is in class **NP** if there exists some deterministic Turing machine $M$ and another problem $B(x,y)$ such that: > - $M$ runs in polynomial time in $x$ on all inputs $(x,y)$. > - for all solutions $x$ to $A$, there exists some input $y$ of size polynomial in $x$ such that $M$ outputs 'yes' for $B$. > - for all other inputs $\neg x$ and all inputs $y$ of size polynomial in $x$, $M$ outputs 'no' for $B$. > > Alternatively, all decision problems of class NP are *solvable* in polynomial time by a nondeterministic Turning machine but are only *verifiable* in polynomial time by a deterministic one. The input $y$ corresponding to a solution $x$ is known as the *certificate* and certifies that $x$ is in fact a solution to $A$. The problem $B$ is known as the *certifier* or *verifier*. Nondeterministic polynomial time is trivially a [[Subset#^5c54ca|superset]] of [[polynomial time]] but it is not yet known whether it is a *proper superset*, implying $\mathsf{P\neq NP}$, or if the two complexity classes are equal, i.e. $\mathsf{P=NP}$. This is known as the P vs NP problem. There additionally exists problems of class [[NP-complete]] and [[NP-hard]]. NP-complete problems are a *subset* of NP and form the intersection between NP and NP-hard problems. ![[NPEulerDiagram.svg]]