查看“︁NC (复杂度)”︁的源代码

{{unsolved|数学|<nowiki>NC = P成立吗？</nowiki>}}
在[[计算复杂度理论]]，'''NC'''（Nick's Class），是一个复杂度类，是能被[[并行计算|并行计算机]]在[[多对数函数]]时间（''[[大O符号|O]]''(log<sup>''c''</sup>&nbsp;''n'')）内以[[多项式空间]]（或者说''[[大O符号|O]]''(''n''<sup>''k''</sup>)并行线程）下解决的[[判定问题]]的集合，最先由[[史提芬·古克]]提出。<ref name=AB120>Arora & Barak (2009) p.120</ref> 

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

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

'''[[RNC (复杂度)|RNC]]'''是随机化方向的对NC的扩展。
== NC谱系 ==
在[[计算复杂度理论]]，'''NC'''<sup>''i''</sup>，是一个复杂度类，是能被[[并行计算|并行计算机]]在''[[大O符号|O]]''(log<sup>''i''</sup>&nbsp;''n'')时间内以[[多项式空间]]下解决的[[判定问题]]的集合，那么明显地有以下性质：
*<math>\mathbf{NC}^1 \subseteq \mathbf{NC}^2 \subseteq \cdots \subseteq \mathbf{NC}^i \subseteq \cdots \mathbf{NC}</math>
此之为'''NC谱系'''。如果考虑和'''[[L (复杂度)|L]]'''，'''[[NL (复杂度)|NL]]'''和'''[[AC (复杂度)|AC]]'''的话那么有：
*<math> \mathbf{NC}^1 \subseteq \mathbf{L} \subseteq \mathbf{NL} \subseteq \mathbf{AC}^1 \subseteq \mathbf{NC}^2 \subseteq \mathbf{P}.</math>
*<math>\mathbf{NC}^i \subseteq \mathbf{AC}^i \subseteq \mathbf{NC}^{i+1}.</math><ref name=AB118/><ref name=CK437>Clote & Kranakis (2002) p.437</ref>
**这直接导致了'''NC = AC'''。即使是对于'''i = 0'''也是严格成立的。<ref name=CK12>Clote & Kranakis (2002) p.12</ref>
=== 未解问题：NC階層是否真階層？ ===
一个主要的而悬而未决的问题是，[[计算复杂度理论]]（的某些部分）对于NC谱系是否真的适用。
Papadimitriou发现，如果设存在某些''i''令
*'''NC'''<sup>''i''</sup> = '''NC'''<sup>''i''+1</sup>
那么对于一切''j ≥ i''均存在
*'''NC'''<sup>''i''</sup> = '''NC'''<sup>''j''</sup>
*并最终导致'''NC'''<sup>''i''</sup> = '''NC'''
这一命题被称之为'''NC谱系崩塌'''，因为根据'''NC谱系'''链有
*<math>\textbf{NC}^1 \subseteq \textbf{NC}^2 \subseteq \cdots</math>
这意味着NC谱系有可能会崩塌到某个i值。对于这个问题，有两种可能性：

# <math>\textbf{NC}^1 \subset \cdots \subset \textbf{NC}^i \subset ... \subset \textbf{NC}^{i+j} \subset \cdots \textbf{NC}</math>
# <math>\textbf{NC}^1 \subset \cdots \subset \textbf{NC}^i = ... = \textbf{NC}^{i+j} = \cdots \textbf{NC}</math>

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

== 参考资料 ==
{{Reflist|}}
{{复杂度类}}

[[Category:复杂度类]]
[[Category:计算机科学中未解决的问题]]