PSPACE完全性

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