Math Conjectures

PP versus NCNC

OPENLandmarkOpen problemProposed c. 1980 · Standard version

Canonical statement

Is
NC≠P? NC\ne P?
Here NC=⋃k≥1NCkNC=\bigcup_{k\geq1}NC^k, and NCkNC^k consists of languages decided by logspace-uniform families of polynomial-size Boolean circuits with bounded fan-in and depth O(log⁡kn)O(\log^k n); PP is deterministic polynomial time.
View source LaTeX
Is
\[
  NC\ne P?
\]
Here \(NC=\bigcup_{k\geq1}NC^k\), and \(NC^k\) consists of languages
decided by logspace-uniform families of polynomial-size Boolean circuits
with bounded fan-in and depth \(O(\log^k n)\); \(P\) is deterministic
polynomial time.
TCS-005:[Cook1985NC][GreenlawHooverRuzzo1995][AroraBarak2009]
Theoretical computer scienceNumerical analysis

Notes

The problem asks whether everything solvable in polynomial time can also be solved by fast parallel algorithms: is NCNC, the class of languages decided by uniform polynomial-size Boolean circuits of polylogarithmic depth and bounded fan-in, strictly contained in PP? The question emerged around 1980 with the systematic study of parallel computation and was articulated in Cook's taxonomy of problems with fast parallel algorithms [Cook1985NC].

The containment NC⊆PNC\subseteq P is immediate, and PP-completeness under logspace reductions plays the role here that NPNP-completeness plays for PP versus NPNP: problems such as the circuit value problem are PP-complete, so NC=PNC=P if and only if any one of them admits polylogarithmic-depth circuits, and many such problems are catalogued and believed inherently sequential [GreenlawHooverRuzzo1995]. Proving that even a single PP-complete problem lies outside NCNC, however, would require circuit-depth lower bounds against polynomial-size circuits far beyond current general techniques [AroraBarak2009].

The problem is open in both directions: a separation demands new depth lower bounds, while a collapse would require parallelizing computations that appear inherently sequential.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.