復雜性類

在計算復雜性理論中，復雜性類是一組基于資源的相關復雜性的計算問題。兩種最常分析的資源是時間和內存。一般來說，一個復雜度類是以一種計算問題的類型、一種計算模型和一種有約束的資源如時間或內存來定義的。特別是，大多數復雜性類由圖靈機可解決的決策問題組成，并以其時間或空間（內存）要求來區分。例如，P類是可由確定性圖靈機在多項式時間內解決的決策問題的集合。然而，還有許多復雜性類是以其他類型的問題（如計數問題和函數問題）和使用其他計算模型來定義的。對復雜性等級之間關系的研究是理論計算機科學的一個主要研究領域。復雜性類通常有一般的層次，例如，已知一些基本的時間和空間復雜性類以下列方式相互聯系。NL?P?NP?PACE?EXPTIME?EXPSPACE（其中?表示子集關系）。然而，許多關系還不為人所知；例如，計算機科學中最有名的開放問題之一是關于P是否等于NP的問題。類之間的關系常常回答關于計算的基本性質的問題。例如，P與NP的問題直接關系到非確定性是否給計算機增加了任何計算能力，以及具有可以快速檢查正確性的解決方案的問題是否也可以被快速解決。

復雜性類是相關計算問題的集合。它們被定義為在特定的計算資源如時間或內存方面，解決其中所包含的問題的計算難度。更正式地說，復雜性類的定義包括三件事：一種計算問題的類型，一種計算模型，以及一種受限的計算資源。特別是，大多數復雜度類是由圖靈機在有限的時間或空間資源下可以解決的決策問題組成的。例如，復雜性類P被定義為可由確定性圖靈機在多項式時間內解決的決策問題的集合。

直觀地說，計算問題只是一個可以用算法解決的問題。例如，自然數是n{displaystylen}是素數嗎？就是一個計算問題。一個計算問題在數學上被表示為問題的答案集合。

理論計算機科學中最常分析的問題是決策問題--那種可以被提出來作為是-否問題的問題。例如，上面的首要性例子就是一個決策問題的例子，因為它可以用是-否問題來表示，就是自然數素數。就計算理論而言，一個決策問題被表示為運行正確算法的計算機會回答是的輸入字符串的集合。是代表自然數的字符串集合，當輸入到一臺運行正確測試素數的算法的計算機中時，該算法會回答是，這個數字是素數。這種"是"-"否"的格式通常被等效為接受-拒絕；也就是說，如果決策問題的答案是"是"，算法就接受輸入的字符串，如果答案是"否"，算法就拒絕。雖然有些問題不容易被表達為決策問題，但它們還是包含了廣泛的計算問題。