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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 10: Строка 10:
 
== Связь класса ''PS'' с другими классами теории сложности ==
 
== Связь класса ''PS'' с другими классами теории сложности ==
  
=== ''P '' ''PS'' ===
+
=== ''P '' ''PS'' ===
 
====Доказательство:====
 
====Доказательство:====
  
 
Машина Тьюринга <tex>m</tex>, распознающая язык из <tex>P</tex> за полиномиальную величину времени не успеет использовать память, размер которой превосходит полиномиальное значение.  
 
Машина Тьюринга <tex>m</tex>, распознающая язык из <tex>P</tex> за полиномиальную величину времени не успеет использовать память, размер которой превосходит полиномиальное значение.  
  
=== ''NP '' ''PS'' ===
+
=== ''NP '' ''PS'' ===
 
====Доказательство:====
 
====Доказательство:====
  

Версия 20:42, 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(i*n^i)[/math]

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

P PS

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

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

NP PS

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

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


Класс NPS

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