空间复杂性类/ space complexity class // space complexity class /
空间复杂性（space complexity）研究计算各种问题所需要的空间资源。在讨论空间复杂性的场合，人们使用的图灵机一般包含一条只读的输入带(input tape)、一条可读可写的工作带(work tape)和一条只写的输出带(output tape)。而所需的空间资源就是指计算过程中使用工作带的大小。给定函数，用表示所有能由（确定）图灵机在空间内能够判定的问题构成的类；而包括所有非确定图灵机在空间内能够判定的问题（见复杂性类）。类似时间复杂性的研究，人们定义了很多空间复杂性类。其中最著名的包括多项式空间类（见多项式空间PSPACE类）、非确定对数空间类（见非确定对数空间NL类）和对数空间类（见对数空间L类）。
非确定对数空间NL类/ nondeterministic logarithmic space /nondeterministic logarithmic space
空间复杂性类非确定图灵机在对数空间里可以求解的判定问题类。多项式空间PSPACE类/ polynomial space class PSPACE /polynomial space class PSPACE
空间复杂性类多项式空间PSPACE类包含所有图灵机在多项式空间(polynomial space)里可以求解的判定问题。PSPACE类是指数时间EXP类的子类，同时它的子类包括多项式时间P类、非确定多项式时间NP类以及多项式谱系PH等。
京公网安备 11010202008139号