Класс PS. Связь класса PS с другими классами теории сложности
НЕТ ВОЙНЕ |
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Определение
Определение: |
. | — класс языков, разрешимых на детерминированной машине Тьюринга с использованием памяти полиномиального размера.
Определение: |
. | — класс языков, разрешимых на недетерминированной машине Тьюринга с использованием памяти полиномиального размера.
Связь класса PS с другими классами теории сложности
Теорема: |
. |
Доказательство: |
Рассмотрим любой язык | из . Так как , то существует машина Тьюринга , распознающая за полиномиальное время. Это значит, что не сможет использовать более, чем полиномиальное количество памяти, следовательно .
Теорема: |
. |
Доказательство: |
Рассмотрим любой язык | из . Так как , то существует программа-верификатор , что для каждого слова из (и только для них) существует такой сертификат полиномиальной длины, что допускает слово и сертификат. Тогда, чтобы проверить принадлежность слова языку, мы можем перебрать все сертификаты полиномиальной длины. Для этого необходим полиномиальный размер памяти. Из этого следует, что .