Список обозначений

NP-доказательство

$\mathrm{NP}$-proof

Пусть $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\}$.

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна