Бинарное отношение $R$ на множестве $\{0,1\}^*$ (т. е. подмножество $\{0,1\}^*\times\{0,1\}^*$) называется $\mathrm{NP}$-отношением, если

существует полином $p$ такой, что $\lvert{y}\rvert\leqslant p(\lvert{x}\rvert)$ для любой пары $(x,y)\in R$ (это свойство называется полиномиальной ограниченностью или полиномиальной уравновешенностью);
$R$ распознаваемо некоторым полиномиальным детерминированным алгоритмом.

Каждому бинарному отношению $R$ на множестве $\{0,1\}^*$ соответствует язык $L_R=\{x\in\{0,1\}^*\,|\,\exists\,y\in\{0,1\}^* (x,y)\in R\}$. Тогда $\mathrm{NP}$ — это в точности класс всех языков вида $L_R$, где $R$ пробегает всевозможные $\mathrm{NP}$-отношения. Этим объясняется происхождение термина «$\mathrm{NP}$-отношение».