Класс PS — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Определение == Классом <math>PS (PSPACE)\,\!</math> называется множество языков, распознаваемых дете…»)
 
м (rollbackEdits.php mass rollback)
 
(не показано 20 промежуточных версий 4 участников)
Строка 1: Строка 1:
 
== Определение ==
 
== Определение ==
  
Классом <math>PS (PSPACE)\,\!</math> называется множество языков, распознаваемых детерминированной машиной Тьюринга с полиномиально ограниченной памятью.
+
Классом <tex>PS (PSPACE)\,\!</tex> называется множество языков, распознаваемых детерминированной машиной Тьюринга с полиномиально ограниченной памятью.
 
   
 
   
<math>PS=\{L \mid \exists \ m: L(m)=L, S(m, x) \le poly(|x|) \} </math>, где <math>m-\,\!</math> детерминированная машина Тьюринга, <math>S-\,\!</math> расход памяти, <math>|x|-\,\!</math> длина <math>x\,\!</math>.
+
<tex>PS=\{L \mid \exists \ m: L(m)=L, S(m, x) \le poly(|x|) \} </tex>, где <tex>m-\,\!</tex> детерминированная машина Тьюринга, <tex>S-\,\!</tex> расход памяти, <tex>|x|-\,\!</tex> длина <tex>x\,\!</tex>.
  
 
== Альтернативное определение ==
 
== Альтернативное определение ==
<math> PS=\bigcup_{i=0}^\infty DSPACE(i*n^i)</math>
+
<tex> PS=\bigcup_{i=0}^\infty DSPACE(in^i)</tex>
 +
 
 +
== Связь класса ''PS'' с другими классами теории сложности ==
 +
 
 +
=== ''P'' ⊆ ''PS'' ===
 +
====Доказательство====
 +
 
 +
Машина Тьюринга <tex>m</tex>, распознающая язык из <tex>P</tex> за полиномиальную величину времени не успеет использовать память, размер которой превосходит полиномиальное значение.
 +
 
 +
=== ''NP'' ⊆ ''PS'' ===
 +
====Доказательство====
 +
 
 +
Для перебора всех сертификатов полиномиальной длины, необходим полиномиальный размер памяти. Тогда любой язык из <tex>NP</tex> принадлежит <tex>PS</tex>
 +
 
 +
Заметим также, что
 +
=== ''L'' ⊆ ''P'' ===
 +
====Доказательство====
 +
 
 +
Машина Тьюринга, распознающая язык <tex>L=DSPACE(c \log n)</tex> работает не более чем <tex>| \Sigma |^{c\log n}=poly(n) </tex> времени.
 +
 
 +
=== Вывод ===
 +
----
 +
<tex> L \subseteq P \subseteq NP \subseteq PS </tex>
 +
 
 +
По [[Теорема о емкостной иерархии|теореме о емкостной иерархии]] <tex> L \neq PS </tex>. Так что хотя бы одно из рассмотренных включений — строгое, но неизвестно, какое. В настоящий момент общепринятая точка зрения, что все приведенные включения - строгие.
 +
 
 +
== Класс ''NPS'' ==
 +
 
 +
Классом <tex>NPS (NPSPACE)\,\!</tex> называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью.
 +
 
 +
В соответствии с [[Теорема Сэвича. Совпадение классов NPS и PS#Теорема Сэвича|теоремой Сэвича]] <tex>PS=NPS</tex>, поэтому обычно в теории сложности оперируют с классом <tex>PS</tex>.

Текущая версия на 19:38, 4 сентября 2022

Определение

Классом [math]PS (PSPACE)\,\![/math] называется множество языков, распознаваемых детерминированной машиной Тьюринга с полиномиально ограниченной памятью.

[math]PS=\{L \mid \exists \ m: L(m)=L, S(m, x) \le poly(|x|) \} [/math], где [math]m-\,\![/math] детерминированная машина Тьюринга, [math]S-\,\![/math] расход памяти, [math]|x|-\,\![/math] длина [math]x\,\![/math].

Альтернативное определение

[math] PS=\bigcup_{i=0}^\infty DSPACE(in^i)[/math]

Связь класса PS с другими классами теории сложности

PPS

Доказательство

Машина Тьюринга [math]m[/math], распознающая язык из [math]P[/math] за полиномиальную величину времени не успеет использовать память, размер которой превосходит полиномиальное значение.

NPPS

Доказательство

Для перебора всех сертификатов полиномиальной длины, необходим полиномиальный размер памяти. Тогда любой язык из [math]NP[/math] принадлежит [math]PS[/math]

Заметим также, что

LP

Доказательство

Машина Тьюринга, распознающая язык [math]L=DSPACE(c \log n)[/math] работает не более чем [math]| \Sigma |^{c\log n}=poly(n) [/math] времени.

Вывод


[math] L \subseteq P \subseteq NP \subseteq PS [/math]

По теореме о емкостной иерархии [math] L \neq PS [/math]. Так что хотя бы одно из рассмотренных включений — строгое, но неизвестно, какое. В настоящий момент общепринятая точка зрения, что все приведенные включения - строгие.

Класс NPS

Классом [math]NPS (NPSPACE)\,\![/math] называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью.

В соответствии с теоремой Сэвича [math]PS=NPS[/math], поэтому обычно в теории сложности оперируют с классом [math]PS[/math].