Изменения

Перейти к: навигация, поиск

Классы NP, coNP, Σ₁, Π₁

3 байта убрано, 13:11, 22 марта 2016
Определение: вернул псевдокод на место
: Пусть <tex>L \in \mathrm{\Sigma_1}</tex>. Тогда существуют <tex>R(x,y)</tex> и полином <tex>p</tex> из определения <tex>\mathrm{\Sigma_1}</tex>. Построим недетерминированную программу <tex>q(x)</tex>, разрешающую <tex>L</tex>.
: q(x):: y = <tex>\{0,1\}^{p(|x|)}</tex>: '''return''' R(x,y)
: Если <tex>x\in L</tex>, то программа сможет «угадать» подходящий сертификат. Если <tex>x\notin L</tex>, то подходящего сертификата не существует по определению. # : Таким образом, <tex>q</tex> разрешает <tex>L</tex>, следовательно <tex>L\in \mathrm{NP}</tex>.
<tex>\gets \quad(\mathrm{NP} \subset \mathrm{\Sigma_1})</tex>.
130
правок

Навигация