Изменения
Нет описания правки
Пусть <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>\leftarrow?\{0,1\}^{\le p(|x|)}</tex> return <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>:
r(x):
return p(x) <tex>\&\&</tex> q(x)
2. Построим программу <tex>r</tex>, разрешающую <tex>L_1\cup L_2</tex>:
r(x):
3. Построим программу <tex>r</tex>, разрешающую <tex>L_1L_2</tex>:
r(x):
n ← <tex>\leftarrow|x|</tex> mid x<tex>\leftarrow?|</tex> mid ←? {1..n} return p(x[1..mid]) <tex>\&\&</tex> q(x[mid+1..n])
4. Построим программу <tex>r</tex>, разрешающую <tex>L_1^*</tex>:
r(x):
n ← <tex>\leftarrow|x|</tex> prev x<tex>\leftarrow|</tex> prev ← 1
do
cur <tex>\leftarrow←?</tex> {prev..n}
if (!p(x[prev..cur]))
return false
prev <tex>\leftarrow</tex> ← cur+1
while (cur != n)
return true
* Задача о клике;
* [http://arxiv.org/abs/cs.CC/0210020 Тетрис]
Все эти языки также являются [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полными]]. О существовании По [[Теорема Ладнера|теореме Ладнера]] существует язык из <tex>\mathrm{NP}</tex> языка, не являющегося являющийся <tex>\mathrm{NP}</tex>-полным гласит [[Теорема Ладнера|теорема Ладнера]].
== Связь P и NP ==
