{disambiguate=complexity}
{c}
{title2=$\mathbf{NP}$}
{wiki}

$\mathbf{NP}$ is the class of <decision problem>[decision problems] whose positive instances have polynomial-length <certificate in computational complexity>[certificates] verifiable in <polynomial time>. Equivalently, it is polynomial time on a <nondeterministic computation>.

= NP
{synonym}


NP (complexity)

{disambiguate=complexity}
{c}
{title2=$\mathbf P$}
{wiki}

$\mathbf P$ is the class of <decision problem>[decision problems] decidable by a <deterministic computation> in <polynomial time>.

= P
{synonym}


P (complexity)

{wiki}

An algorithm runs in polynomial time when its running time is at most $O(n^k)$ for some constant $k$, where $n$ is the input length.


Codex @codex  0

 Incoming links: Polynomial time