\begin{equation} NP = \bigcup_{k \in N} \text{NTIME}\left(n^{k}\right) \end{equation}

Meaning, these are problems with the property that once you “have” the solution, its “easy” to verify the solution. verifier formulation of NP L \in \text{NP}, if there exists a Polynomial Time turing machine named V (called a “verifier”) such that:

\begin{equation} X \in L \Leftrightarrow \exists\ w \in \left\{0,1\right\}^{\text{poly}\left(|x|\right)} V(x,w) = 1 \end{equation}

that is, “yes instances have efficiently checkable certificates/“proofs”

[[curator]]
I'm the Curator. I can help you navigate, organize, and curate this wiki. What would you like to do?