NL完全性

（理学 | 计算机科学技术）

NL完全性（NL-completeness），理学-计算机科学技术-计算机科学理论-计算复杂性-归约，NL完全性刻画了非确定对数空间NL类中在对数空间归约下最难的一类问题。一个判定问题是非确定对数空间NL完全的，当且仅当它满足如下两个条件：①此问题能在非确定对数空间内求解，即它落在类内。②所有类里的问题都能在（确定）对数空间（见对数空间L类）内归约到此问题。