複雜性類

在計算複雜性理論中，通常將計算問題按照難度分成不同的類，這就是複雜性類。也就是說，複雜性類是一些具有類似複雜度的問題的集合。

基本介紹

• 中文名：複雜性類
• 外文名：complexity class
• 所屬學科：計算機科學技術
• 公布時間：2018年

定義

常見的複雜性類定義形式為：可以被某一種計算模型 M 使用 O(f(n)) 的某種資源（如時間、空間）所解決的問題的集合。（其中 n 為輸入編碼的長度）。經典的複雜性類例如 P：可以被確定性圖靈機在多項式時間內解決的決定性問題的集合、NP：可以被非確定性圖靈機在多項式時間內解決的決定性問題的集合、PSPACE（確定性多項式空間類）、Logspace（確定性對數空間類）等。

出處

《計算機科學技術名詞 》第三版。