Класс PS — различия между версиями
Rinatvr (обсуждение | вклад) (Новая страница: «== Определение == Классом <math>PS (PSPACE)\,\!</math> называется множество языков, распознаваемых дете…») |
Rinatvr (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Определение == | == Определение == | ||
| − | Классом < | + | Классом <tex>PS (PSPACE)\,\!</tex> называется множество языков, распознаваемых детерминированной машиной Тьюринга с полиномиально ограниченной памятью. |
| − | < | + | <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>. |
== Альтернативное определение == | == Альтернативное определение == | ||
| − | < | + | <tex> PS=\bigcup_{i=0}^\infty DSPACE(i*n^i)</tex> |
| + | |||
| + | == Связь класса ''PS'' с другими классами теории сложности == | ||
| + | |||
| + | === ''P '' ∈ ''PS'' === | ||
| + | |||
| + | === ''NP '' ∈ ''PS'' === | ||
| + | |||
| + | === ''L '' ∈ ''P'' === | ||
| + | |||
| + | == Класс ''NPS'' == | ||
| + | |||
| + | Классом <tex>NPS (NPSPACE)\,\!</tex> называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью. | ||
Версия 22:43, 16 марта 2010
Содержание
Определение
Классом называется множество языков, распознаваемых детерминированной машиной Тьюринга с полиномиально ограниченной памятью.
, где детерминированная машина Тьюринга, расход памяти, длина .
Альтернативное определение
Связь класса PS с другими классами теории сложности
P ∈ PS
NP ∈ PS
L ∈ P
Класс NPS
Классом называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью.
