Изменения
→Теорема о двух эквивалентных определениях NP (NP = Sigma1)
Оракул — абстракция, вычисляющая за <tex>O(1)</tex> времени, верно ли, что <tex>x</tex> принадлежит множеству <tex>A</tex>.
}}
Сложностный класс задач, решаемых алгоритмом из класса <tex>\mathrm{C}</tex> с оракулом для языка <tex>\mathrm{A}</tex>, обозначают <tex>\mathrm{C^A}</tex>.Если <tex>\mathrm{A}</tex> — множество языков, то <tex>\mathrm{C^A} =\bigcup\limits_{D \in A}\mathrm{C^D}</tex>.
== Класс PS ==
<tex>\mathrm{PS}=\bigcup\limits_{p(n) \in poly} \mathrm{DSPACE}(p(n))</tex>.
}}
== PS-полная задача ==
== Класс P/poly ==
{{Определение
|definition=
Пусть <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>.
{{ Теорема
|statement = Существуют такие оракулы <tex>A</tex> и <tex>B</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex> и <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex>.
}}
{{ Утверждение
| statement = Если существует решение вопроса равенства <tex>\mathrm{P}</tex> и <tex> \mathrm{NP}</tex>, то оно не должно «релятивизоваться».
}}
