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