---
title: "Non-Polynomial Time"
source: https://www.jemoka.com/posts/kbhnon_polynomial_time/
---

\begin{equation} NP = \bigcup_{k \in N} \text{NTIME}\qty(n^{k}) \end{equation}
Meaning, these are problems with the property that once you &ldquo;have&rdquo; the solution, its &ldquo;easy&rdquo; to verify the solution.
verifier formulation of NP \(L \in \text{NP}\), if there exists a Polynomial Time turing machine named \(V\) (called a &ldquo;verifier&rdquo;) such that:
\begin{equation} X \in L \Leftrightarrow \exists\ w \in \qty {0,1}^{\text{poly}\qty(|x|)} V(x,w) = 1 \end{equation}
that is, &ldquo;yes instances have efficiently checkable certificates/&ldquo;proofs&rdquo;
