NC (複雜度)

在計算複雜度理論，NC（Nick's Class），是一個複雜度類，是能被並行計算機在多對數函數時間（O(log^c n)）內以多項式空間（或者說O(n^k)並行線程）下解決的判定問題的集合，最先由史提芬·古克提出。

正如P被認為是易解複雜度類一般，NC也被認為是在並行計算上易解的問題。明顯的有NC ⊆ P，因為一切並行計算都可以以多項式空間依次的在確定型圖靈機上運行。我們目前仍未知道的一個關鍵問題是，NC = P是否成立。大多數的研究人員都認為這是不可能的——否則的話這意味着一切可計算函數都可以並行計算化。正如NP完全對於P來說是懷疑難解複雜度類一樣，P完全對於NC來說也是「懷疑難解」的。

定義中的並行計算機,可以看作為一個並行，公共的PRAM池，所有的並行線程都可以在任意時間訪問池的任意位置，NC的定義不受是否可以同時訪問的影響，當然無論是CRCW，CREW還是EREW都是不受影響的。

RNC是隨機化方向的對NC的擴展。

NC譜系

在計算複雜度理論，NCⁱ，是一個複雜度類，是能被並行計算機在O(logⁱ n)時間內以多項式空間下解決的判定問題的集合，那麼明顯地有以下性質：

• $\mathbf {NC} ^{1}\subseteq \mathbf {NC} ^{2}\subseteq \cdots \subseteq \mathbf {NC} ^{i}\subseteq \cdots \mathbf {NC}$

此之為NC譜系。如果考慮和L，NL和AC的話那麼有：

• $\mathbf {NC} ^{1}\subseteq \mathbf {L} \subseteq \mathbf {NL} \subseteq \mathbf {AC} ^{1}\subseteq \mathbf {NC} ^{2}\subseteq \mathbf {P} .$
• $\mathbf {NC} ^{i}\subseteq \mathbf {AC} ^{i}\subseteq \mathbf {NC} ^{i+1}.$
  • 這直接導致了NC = AC。即使是對於i = 0也是嚴格成立的。

未解問題：NC階層是否真階層？

一個主要的而懸而未決的問題是，計算複雜度理論（的某些部分）對於NC譜系是否真的適用。 Papadimitriou發現，如果設存在某些i令

• NCⁱ = NCⁱ⁺¹

那麼對於一切j ≥ i均存在

• NCⁱ = NC^j
• 並最終導致NCⁱ = NC

這一命題被稱之為NC譜系崩塌，因為根據NC譜系鏈有

• ${\textbf {NC}}^{1}\subseteq {\textbf {NC}}^{2}\subseteq \cdots$

這意味着NC譜系有可能會崩塌到某個i值。對於這個問題，有兩種可能性：

1. ${\textbf {NC}}^{1}\subset \cdots \subset {\textbf {NC}}^{i}\subset ...\subset {\textbf {NC}}^{i+j}\subset \cdots {\textbf {NC}}$
2. ${\textbf {NC}}^{1}\subset \cdots \subset {\textbf {NC}}^{i}=...={\textbf {NC}}^{i+j}=\cdots {\textbf {NC}}$

人們目前普遍認為（1）正確的，雖然還沒有什麼確切的證據。