複雜度類基於資源的複雜性相關的計算複雜性理論中的一系列問題 / 維基百科,自由的 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)。 布盧姆複雜度則不需實際抽象機器就可定義複雜度類。