NC (复杂度)

在计算复杂度理论，NC（Nick's Class），是一个复杂度类，是能被并行计算机在多对数函数时间（O(log^c n)）内以多项式空间（或者说O(n^k)并行线程）下解决的判定问题的集合，最先由史提芬·古克提出。^[1]

正如P被认为是易解复杂度类一般，NC也被认为是在并行计算上易解的问题。^[2]明显的有NC ⊆ P，因为一切并行计算都可以以多项式空间依次的在确定型图灵机上运行。我们目前仍未知道的一个关键问题是，NC = P是否成立。大多数的研究人员都认为这是不可能的——否则的话这意味着一切可计算函数都可以并行计算化。正如NP完全对于P来说是怀疑难解复杂度类一样，P完全对于NC来说也是“怀疑难解”的。

定义中的并行计算机,可以看作为一个并行，公共的PRAM池，所有的并行线程都可以在任意时间访问池的任意位置，NC的定义不受是否可以同时访问的影响，当然无论是CRCW，CREW还是EREW都是不受影响的。

RNC是随机化方向的对NC的扩展。

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）正确的，虽然还没有什么确切的证据。

参考资料

1. Arora & Barak (2009) p.120
2. Arora & Barak (2009) p.118
3. Clote & Kranakis (2002) p.437
4. Clote & Kranakis (2002) p.12