Пусть $R$ — $\mathrm{NP}$-отношение. Тогда $\mathrm{NP}$-доказательством для $x\in\{0,1\}^*$ относительно $R$ называется всякий элемент $y\in\{0,1\}^*$ такой, что $(x,y)\in R$. Очевидно, что $\mathrm{NP}$-доказательство для $x\in\{0,1\}^*$ относительно $R$ существует тогда и только тогда, когда $x\in L_R=\{x\,|\,\exists\,y (x,y)\in R\}$.