NC (复杂度)

在计算复杂度理论，NCⁱ，是一个复杂度类，是能被并行计算机在O(logⁱ n)时间内以多项式空间下解决的判定问题的集合，那么明显地有以下性质：

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

此之为NC谱系。如果考虑和L，NL和AC的话那么有：

• ${\displaystyle \mathbf {NC} ^{1}\subseteq \mathbf {L} \subseteq \mathbf {NL} \subseteq \mathbf {AC} ^{1}\subseteq \mathbf {NC} ^{2}\subseteq \mathbf {P} .}$ 
• ${\displaystyle \mathbf {NC} ^{i}\subseteq \mathbf {AC} ^{i}\subseteq \mathbf {NC} ^{i+1}.}$ ^[2][3]
  • 这直接导致了NC = AC。即使是对于i = 0也是严格成立的。^[4]

未解问题：NC阶层是否真阶层？

一个主要的而悬而未决的问题是，计算复杂度理论（的某些部分）对于NC谱系是否真的适用。 Papadimitriou发现，如果设存在某些i令

• NCⁱ = NCⁱ⁺¹

那么对于一切j ≥ i均存在

• NCⁱ = NC^j
• 并最终导致NCⁱ = NC

这一命题被称之为NC谱系崩塌，因为根据NC谱系链有

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

这意味着NC谱系有可能会崩塌到某个i值。对于这个问题，有两种可能性：

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

人们目前普遍认为（1）正确的，虽然还没有什么确切的证据。