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

Класс PS

Определение

Определение:

[math]\mathrm{PS}[/math] [math]\mathrm{(PSPACE)}[/math] — класс языков, разрешимых на детерминированной машине Тьюринга с использованием памяти полиномиального размера. [math]\mathrm{PS}=\bigcup\limits_{p(n) \in poly} \mathrm{DSPACE}(p(n))[/math].

Определение:

[math]\mathrm{NPS}[/math] [math]\mathrm{(NPSPACE)}[/math] — класс языков, разрешимых на недетерминированной машине Тьюринга с использованием памяти полиномиального размера. [math]\mathrm{NPS}=\bigcup\limits_{p(n) \in poly} \mathrm{NSPACE}(p(n))[/math].

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

Теорема:

[math]\mathrm{P} \subseteq \mathrm{PS}[/math].

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

[math]\triangleright[/math]

Рассмотрим любой язык [math]L[/math] из [math]\mathrm{P}[/math]. Так как [math]L \in \mathrm{P}[/math], то существует машина Тьюринга [math]m[/math], распознающая [math]L[/math] за полиномиальное время. Это значит, что [math]m[/math] не сможет использовать более, чем полиномиальное количество памяти, следовательно [math] L \in \mathrm{PS}[/math].

[math]\triangleleft[/math]

Теорема:

[math]\mathrm{NP} \subseteq \mathrm{PS}[/math].

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

[math]\triangleright[/math]

Рассмотрим любой язык [math]L[/math] из [math]\mathrm{NP}[/math]. Так как [math]L \in \mathrm{NP}[/math], то существует программа-верификатор [math]R(x,y)[/math], что для каждого слова из [math]L[/math] (и только для них) существует такой сертификат [math]y[/math] полиномиальной длины, что [math]R[/math] допускает слово и сертификат. Тогда, чтобы проверить принадлежность слова языку, мы можем перебрать все сертификаты полиномиальной длины. Для этого необходим полиномиальный размер памяти. Из этого следует, что [math]L \in \mathrm{PS}[/math].

[math]\triangleleft[/math]