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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Вывод)
Строка 28: Строка 28:
 
<tex> L \subseteq P \subseteq NP \subseteq PS </tex>
 
<tex> L \subseteq P \subseteq NP \subseteq PS </tex>
  
По теореме о емкостной иерархии <tex> L \neq PS </tex>. Тогда одно из рассмотренных включений - строгое.
+
По теореме [[Теорема о емкостной иерархии|о емкостной иерархии]] <tex> L \neq PS </tex>. Тогда одно из рассмотренных включений - строгое.
  
 
== Класс ''NPS'' ==
 
== Класс ''NPS'' ==
  
 
Классом <tex>NPS (NPSPACE)\,\!</tex> называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью.
 
Классом <tex>NPS (NPSPACE)\,\!</tex> называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью.

Версия 21:37, 31 марта 2010

Определение

Классом [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] называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью.