NC (复杂度)

 未解決的数学問題：NC = P成立吗？

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

NC谱系

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

• ${\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階層是否真階層？

• NCi = NCi+1

• NCi = NCj
• 并最终导致NCi = NC

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

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. ^ Arora & Barak (2009) p.120
2. Arora & Barak (2009) p.118
3. ^ Clote & Kranakis (2002) p.437
4. ^ Clote & Kranakis (2002) p.12