复杂度类基於資源的複雜性相關的計算複雜性理論中的一系列問題 / 维基百科,自由的 encyclopedia 在计算复杂度理论中,一个复杂度类指的是一群复杂度类似的问题的集合。一个典型的复杂度类的定义有以下形式: 可以被同一个抽象机器M使用O(f(n))的资源R所解决的问题的集合(n是输入资料的大小)。 例如NP类别就是一群可以被一非确定型图灵机以多项式时间解决的决定型问题。而P类别则是一群可以被确定型图灵机以多项式时间解决的决定型问题。某些复杂度类是一群函数问题的集合,例如FP (复杂度)(英语:FP (complexity))。 许多复杂度类可为数学逻辑所描述刻划,请见描述性复杂度(英语:descriptive complexity)。 布卢姆复杂度则不需实际抽象机器就可定义复杂度类。
在计算复杂度理论中,一个复杂度类指的是一群复杂度类似的问题的集合。一个典型的复杂度类的定义有以下形式: 可以被同一个抽象机器M使用O(f(n))的资源R所解决的问题的集合(n是输入资料的大小)。 例如NP类别就是一群可以被一非确定型图灵机以多项式时间解决的决定型问题。而P类别则是一群可以被确定型图灵机以多项式时间解决的决定型问题。某些复杂度类是一群函数问题的集合,例如FP (复杂度)(英语:FP (complexity))。 许多复杂度类可为数学逻辑所描述刻划,请见描述性复杂度(英语:descriptive complexity)。 布卢姆复杂度则不需实际抽象机器就可定义复杂度类。