複雜度類 在計算複雜度理論中一個複雜度類指的是一群複雜度類似的問題的集合一個典型的複雜度類的定義有以下形式 可以被同一個抽象機器M使用Ofn的資源R所解決的問題的集合n是輸入資料的大小 例如NP類別就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題而P類別則是一群可以被確定型圖靈機以多項式時間解決的決定型問題某些複雜度類是一群函式問題的集合例如FP 複雜度英语FP complexity 許多複雜度類可為數學邏輯所描述刻劃請見描述性複雜度英语descriptive complexity 布盧姆複雜度則不需實際抽象機器就可定義複雜度類