PSPACE — класс задач, разрешимых на машине Тьюринга, причем существует алгоритм (машина Тьюринга), использующий память не более чем полиномиального размера от длины входа.

Более формально, через определение класса DSPACE:

P S P A C E c > 0 D S P A C E ( n c ) {\cal PSPACE} \equiv \cup_{c>0} {\cal DSPACE}(n^c)


По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.