26
правок
Изменения
Новая страница: « =Класс PS= == Определение == {{Определение |definition=<tex>\mathrm{PS}</tex> <tex>\mathrm{(PSPACE)}</tex> {{---}} класс язы...»
=Класс PS=
== Определение ==
{{Определение
|definition=<tex>\mathrm{PS}</tex> <tex>\mathrm{(PSPACE)}</tex> {{---}} класс языков, разрешимых на детерминированной машине Тьюринга с использованием памяти полиномиального размера. <br>
<tex>\mathrm{PS}=\bigcup\limits_{p(n) \in poly} \mathrm{DSPACE}(p(n))</tex>.
}}
{{Определение
|definition=<tex>\mathrm{NPS}</tex> <tex>\mathrm{(NPSPACE)}</tex> {{---}} класс языков, разрешимых на недетерминированной машине Тьюринга с использованием памяти полиномиального размера. <br>
<tex>\mathrm{NPS}=\bigcup\limits_{p(n) \in poly} \mathrm{NSPACE}(p(n))</tex>.
}}
== Связь класса PS с другими классами теории сложности ==
{{Теорема
|statement =
<tex>\mathrm{P} \subseteq \mathrm{PS}</tex>.
|proof = Рассмотрим любой язык <tex>L</tex> из <tex>\mathrm{P}</tex>. Так как <tex>L \in \mathrm{P}</tex>, то существует машина Тьюринга <tex>m</tex>, распознающая <tex>L</tex> за полиномиальное время. Это значит, что <tex>m</tex> не сможет использовать более, чем полиномиальное количество памяти, следовательно <tex> L \in \mathrm{PS}</tex>.
}}
{{Теорема
|statement =
<tex>\mathrm{NP} \subseteq \mathrm{PS}</tex>.
|proof = Рассмотрим любой язык <tex>L</tex> из <tex>\mathrm{NP}</tex>. Так как <tex>L \in \mathrm{NP}</tex>, то существует программа-верификатор <tex>R(x,y)</tex>, что для каждого слова из <tex>L</tex> (и только для них) существует такой сертификат <tex>y</tex> полиномиальной длины, что <tex>R</tex> допускает слово и сертификат. Тогда, чтобы проверить принадлежность слова языку, мы можем перебрать все сертификаты полиномиальной длины. Для этого необходим полиномиальный размер памяти. Из этого следует, что <tex>L \in \mathrm{PS}</tex>.
}}
