学科分类 - 《中国大百科全书》第三版网络版

高级搜索

专业板块专题板块大众板块

首页 . 理学 . 计算机科学技术

NP完全性/ NP-completeness /NP-completeness
归约
刻画NP类（见非确定多项式时间NP类）中在多项式时间归约下最难的一类问题。
NL完全性/ NL-completeness /NL-completeness
归约
NL完全性刻画了非确定对数空间NL类中在对数空间归约下最难的一类问题。一个判定问题是非确定对数空间NL完全的，当且仅当它满足如下两个条件：①此问题能在非确定对数空间内求解，即它落在类内。②所有类里的问题都能在（确定）对数空间（见对数空间L类）内归约到此问题。
相对化/ relativization /relativization
归约
可计算性理论和计算复杂性理论（见计算复杂性）研究中重要的概念和技术。
P完全性/ P-completeness /P-completeness
归约
P完全性（P-completeness）刻画了多项式时间P类中在对数空间归约（见对数空间L类）下最难的一类问题。
PSPACE完全性/ PSPACE-completeness /PSPACE-completeness
归约
刻画多项式空间PSPACE类中在多项式时间归约下最难的一类问题。

NP完全性/ NP-completeness /NP-completeness