38
правок
Изменения
Новая страница: «== Определение == Классом <math>PS (PSPACE)\,\!</math> называется множество языков, распознаваемых дете…»
== Определение ==
Классом <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>
Классом <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>
