复杂性类
计算机科学技术名词
计算复杂性理论中,通常将计算问题按照难度分成不同的类,这就是复杂性类。也就是说,复杂性类是一些具有类似复杂度的问题的集合。
定义
常见的复杂性类定义形式为:可以被某一种计算模型 M 使用 O(f(n)) 的某种资源(如时间、空间)所解决的问题的集合。(其中 n 为输入编码的长度)。经典的复杂性类例如 P:可以被确定性图灵机在多项式时间内解决的决定性问题的集合、NP:可以被非确定性图灵机在多项式时间内解决的决定性问题的集合、PSPACE(确定性多项式空间类)、Logspace(确定性对数空间类)等。
出处
《计算机科学技术名词 》第三版。
参考资料
最新修订时间:2024-05-21 15:22
目录
概述
定义
出处
参考资料