Класс PS

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Определение

Классом [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 с другими классами теории сложности

P ⊆ PS

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

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

NP ⊆ PS

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

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

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

L ⊆ P

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

Машина Тьюринга, распознающая язык [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].