PSPACE完全性

（计算机科学技术）

PSPACE完全性（PSPACE-completeness），计算机科学技术名词，如果一个多项式空间可识别的语言 A 还满足条件：任意一个多项式空间识别的语言 X 均对数空间多一归约到 A ，则称 A 是多项式空间完全的。量词布尔公式的判定性问题QBF在对数空间多一归约下就是一个PSPACE完全问题。