Изменения

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

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

283 байта убрано, 16:09, 5 июня 2012
Нет описания правки
*<tex>\mathrm{\Sigma_1} \subset \mathrm{NP}</tex>.
Пусть <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>.
<tex>q(x):</tex> y <tex>y\leftarrow?\{0,1\}^{\le p(|x|)}</tex> <tex>return</tex> <tex>R(x,y)</tex>
Если <tex>x\in L</tex>, то программа сможет «угадать» подходящий сертификат. Если <tex>x\notin L</tex>, то подходящего сертификата не существует по определению. Таким образом, <tex>q</tex> разрешает <tex>L</tex>, следовательно <tex>L\in \mathrm{NP}</tex>.
*<tex>\mathrm{NP} \subset \mathrm{\Sigma_1}</tex>.
1. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cap L_2</tex>:
<tex>r(x):</tex> <tex> return</tex> <tex>p(x)</tex> <tex>\&\&</tex> <tex>q(x)</tex>
2. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cup L_2</tex>:
<tex>r(x):</tex> <tex> return</tex> <tex>p(x)</tex> <tex>||</tex> <tex>q(x)</tex>
3. Построим программу <tex>r</tex>, разрешающую <tex>L_1L_2</tex>:
<tex>r(x):</tex> n <tex>n\leftarrow|x|</tex> mid <tex>mid\leftarrow?\</tex> {1..n\}</tex> <tex>return</tex> <tex>p(x[1..mid])</tex> <tex>\&\&</tex> <tex>q(x[mid+1..n])</tex>
4. Построим программу <tex>r</tex>, разрешающую <tex>L_1^*</tex>:
<tex>r(x):</tex> n <tex>n\leftarrow|x|</tex> prev <tex>prev\leftarrow 1</tex>1 <tex>do</tex> cur <tex>cur\leftarrow?\</tex> {prev..n\}</tex> <tex>if</tex> <tex>(!p(x[prev..cur]))</tex> <tex>return</tex> <tex>false</tex> prev <tex>prev\leftarrow cur+1</tex>cur+1 <tex>while</tex> <tex>(cur</tex> <tex>!=</tex> <tex>n)</tex> <tex>return</tex> <tex>true</tex>
<br>
}}
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/24057»

Навигация