Изменения

По одному из определений <math>NP</math> языка, язык <math>L</math> принадлежит <math>NP</math>, если существует такая функция <math>R(x, y) \in \tilde{P}</math> — <math>NP</math>-отношение для языка <math>L</math> (<math>NP</math>-relation), что: <math>x \in L \Leftrightarrow \exists y</math> — такой сертификат для <math>x</math>, что: <math>|y| \le poly(|x|)</math> и <math>R(x, y) = 1</math>. Таким образом, для проверки принадлежности некоторого слова NP языку L с NP-отношением R необходимо предъявить соответствующий сертификат. Так как для любого слова из языка существует подтверждающий сертификат, то существует программа g(x), которая для слов из языка возвращает нужный сертификат. А для слов не из языка никаких гарантий на возвращаемое значение функции нет, и потому она может либо вернуть неправильный сертификат, либо вообще зависнуть.

== Формулировка ==