Papex

Open problem · Computer science · Open

NC versus P

Can every problem solvable in polynomial time be solved in polylogarithmic time on a parallel computer with polynomially many processors?

Summary

NC captures the problems that parallel computers can solve very fast. Whether NC = P is open; most researchers expect some efficiently solvable problems, such as the P-complete ones, to be inherently sequential.

Why it is open

P is the class of problems that can be decided in time n^O(1) on inputs of length n; NC is the class that can be decided in parallel time (log n)^O(1) with n^O(1) processors [5]. Equivalently, an NC problem is recognised by a uniform family of Boolean circuits (networks of logic gates, one for each input length) of polynomial size and polylogarithmic depth; NC^k is the subclass with depth O((log n)^k) [5]. Every problem in NC is in P, and the open question is whether this inclusion is proper [5]. Stephen Cook named the class "Nick's Class" after Nicholas Pippenger, who studied such circuits [5].

The question is usually attacked through P-completeness. A problem is P-complete if it is in P and every problem in P reduces to it by a reduction that is itself highly parallel; if any P-complete problem is in NC, then NC equals P [5]. In 1975 Richard Ladner showed that the circuit value problem, computing the output of a given Boolean circuit on given inputs, is P-complete [1, 5]. NC = P therefore holds exactly if the output of any polynomial-size circuit can be computed in polylogarithmic time with polynomially many processors [5].

A resolution would be an NC algorithm for a P-complete problem, or a proof that none exists. No prize or committee sets the bar; the status here follows Wikipedia's list of unsolved problems in computer science, which lists the "NC = P problem" [14]. Raymond Greenlaw, H. James Hoover and Walter Ruzzo, who argue that NC and P differ, call that evidence "ultimately inconclusive" and note that it is still possible, for example, that NC equals P or even NP [5]. For the related question of P and NP, see the Papex page P versus NP.

What is known

P-complete problems (1975–1995). Besides circuit value, linear programming is P-complete: David Dobkin, Richard Lipton and Steven Reiss reduced a P-complete logic problem to it in 1979 [3, 5]. So is deciding whether a network with integer capacities admits a flow of a given value [5]. Whether linear programming has a strongly polynomial algorithm is a different question, on the Papex page Strongly polynomial linear programming. The phrase "inherently sequential" spread after John Reif's 1985 paper "Depth-first Search is Inherently Sequential", which showed that computing the lexicographically first depth-first search order of a graph is P-complete [5]. Greenlaw, Hoover and Ruzzo's 1995 book catalogues P-complete problems, together with problems whose status was open [5].

Problems in between (1987–2021). Some problems in P are known neither to be in NC nor to be P-complete. Greenlaw and colleagues list among them the greatest common divisor of two integers and depth-first search numbering; for the latter, randomised parallel algorithms (the class RNC, randomised NC) are known [5]. Deciding whether a graph has a perfect matching, a set of edges that pairs up all its vertices, is in RNC, but it is not known whether randomness is needed [12]. Ketan Mulmuley, Umesh Vazirani and Vijay Vazirani found perfect matchings in RNC using their Isolation Lemma: random edge weights make the minimum-weight perfect matching unique with probability at least 1/2 [4, 12]. In 2016 Stephen Fenner, Rohit Gurjar and Thomas Thierauf almost completely derandomised it for bipartite graphs, putting bipartite perfect matching in quasi-NC²: circuits of depth O(log² n) and quasi-polynomial size n^O(log n) [12]. In 2017 Ola Svensson and Jakub Tarnawski extended this to general graphs, with a deterministic algorithm running in O(log³ n) time on n^O(log² n) processors [10].

Space and depth (1977–2026). Allan Borodin related the memory (space) of a Turing machine to circuit depth [2]: a computation in logarithmic space (the class L) can be simulated by polynomial-size circuits of depth O((log n)²), and any NC algorithm can be simulated in polylogarithmic space [5]. The known relations Greenlaw and colleagues list include NC¹ ⊆ L ⊆ SL ⊆ NL ⊆ AC¹ ⊆ NC², where NL is nondeterministic logarithmic space, SL its symmetric variant and AC¹ the class of polynomial-size, logarithmic-depth circuits whose gates may have any number of inputs [5]. In 2008 Omer Reingold gave a deterministic log-space algorithm for connectivity in undirected graphs, which implies SL = L [9]. Whether L equals P is "a long-standing open problem" [5], and in 2026 Wikipedia's list still includes both L = NL and L = P [14]. Proving that some problem in P needs circuits of more than logarithmic depth (P ⊄ NC¹) is "one of the major open problems in complexity theory"; in the 2021 version of their paper, Susanna de Rezende and colleagues give the best depth lower bound for an explicit function as (3 − o(1)) log n, from Johan Håstad's work, not improved for more than two decades except in lower-order terms [13].

Restricted models (1997–1999). For monotone circuits, which use only AND and OR gates, Ran Raz and Pierre McKenzie proved that monotone NC differs from monotone P and that the monotone NC^i hierarchy is strict; only monotone NC¹ ≠ monotone NC² had been known [7]. Mulmuley defined a PRAM model without bit operations that "encompasses virtually all known parallel algorithms for (weighted) combinatorial optimization and algebraic problems", and proved that in it min-cost flow on n vertices cannot be solved in time √n/b with 2^(√n/b) processors, for a large enough constant b, with a similar bound for max-flow [8]. Since these problems are P-complete, he presents this as "concrete support" for the conjecture that P ≠ NC [8].

Main approaches

Depth lower bounds through communication. Mauricio Karchmer and Avi Wigderson observed that the depth of a function equals the communication complexity of an associated two-party game [13]. Karchmer, Raz and Wigderson conjectured that the depth of a composed function f(g(x₁), …, g(x_m)) is roughly the depth of f plus that of g, which would imply P ⊄ NC¹ [6, 13]. Strongest evidence: the conjecture holds for every outer function f when g is the parity function or the "universal relation", and in 2020 de Rezende and colleagues proved its monotone version for every monotone inner function whose monotone depth can be lower-bounded through a lifting theorem [13]. Main difficulty: the best depth bound has stood at about 3 log n for over two decades, and de Rezende and colleagues describe even P ⊄ NC¹ as "an important milestone toward proving lower bounds on general circuits" [13].

Lower bounds in natural restricted models. Model the techniques of known algorithms and prove that they fail [5, 8]. Strongest evidence: Mulmuley's bounds for flow problems [8]; pebbling lower bounds, which show that a natural space-saving way of evaluating circuits needs much space, so that "if pebbling algorithms were the only avenue" to small-space circuit evaluation, NC and P would be distinct [5]. Main difficulty: such evidence, Greenlaw and colleagues write, "does not prove" that a highly parallel simulation of arbitrary sequential computation is impossible [5]; Mulmuley suggested that a proof of P ≠ NC "should somehow use geometric invariant theory in a deep way" [8].

Monotone separations. Prove the separation first for circuits without negation [7]. Strongest evidence: monotone NC ≠ monotone P [7]. Raz and McKenzie's argument gave the first lifting theorem, which turns lower bounds on query complexity into lower bounds on communication [13]; Mika Göös, Toniann Pitassi and Thomas Watson adapted it to obtain gaps for the log-rank conjecture [11]. Main difficulty: the monotone analogue of P ⊄ NC¹ "has been known to hold for a long time", while the non-monotone setting is "far less understood" [13].

Shrinking the middle ground. Place problems of unknown status in NC, or prove them P-complete [5]. Strongest evidence: deterministic quasi-NC algorithms for perfect matching [10, 12]. Main difficulty: derandomising the Isolation Lemma in NC "remains a challenging open question" [12].

Open sub-questions

  1. Matching in NC. Can isolating weights for bipartite graphs be constructed in NC with polynomially bounded values, improving the quasi-polynomial weights of Fenner, Gurjar and Thierauf [12]?
  2. Depth-first search. Can a depth-first search tree of a general graph be constructed in NC, as it can for directed acyclic graphs and in RNC for general graphs [5, 14]?
  3. Integer gcd. Is the greatest common divisor of two n-bit integers in NC? The parallel algorithms listed in 1995 include ones running in time O(n log log n / log n) and O(n / log n) [5].
  4. The multiplexor route. Or Meir showed that a variant of the Karchmer–Raz–Wigderson conjecture, for compositions of every non-constant function with the multiplexor relation, would imply P ⊄ NC¹. Does that variant hold [13]?
  5. Beyond 3 log n. Can the composition theorems proved for monotone inner functions be carried to non-monotone ones, giving depth lower bounds above (3 − o(1)) log n [13]?
  6. More bit operations. Do Mulmuley's lower bounds for min-cost flow and max-flow still hold in a PRAM with more bit operations than parity and one-bit shifts [8]?

Work on this in Papex

If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.

Key references

  1. Ladner, R. E. (1975). The circuit value problem is log space complete for P. ACM SIGACT News 7(1), 18–20. 10.1145/990518.990519 · Checked 16 Oct 2026
  2. Borodin, A. (1977). On relating time and space to size and depth. SIAM Journal on Computing 6(4), 733–744. 10.1137/0206054 · Checked 16 Oct 2026
  3. Dobkin, D., Lipton, R. J. & Reiss, S. (1979). Linear programming is log-space hard for P. Information Processing Letters 8(2), 96–97. 10.1016/0020-0190(79)90152-2 · Checked 16 Oct 2026
  4. Mulmuley, K., Vazirani, U. V. & Vazirani, V. V. (1987). Matching is as easy as matrix inversion. Combinatorica 7(1), 105–113. 10.1007/BF02579206 · Checked 16 Oct 2026
  5. Greenlaw, R., Hoover, H. J. & Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. 10.1093/oso/9780195085914.001.0001 · Checked 16 Oct 2026
  6. Karchmer, M., Raz, R. & Wigderson, A. (1995). Super-logarithmic depth lower bounds via the direct sum in communication complexity. Computational Complexity 5(3–4), 191–204. 10.1007/BF01206317 · Checked 16 Oct 2026
  7. Raz, R. & McKenzie, P. (1999). Separation of the monotone NC hierarchy. Combinatorica 19(3), 403–435; conference version in FOCS 1997, 234–243, DOI 10.1109/SFCS.1997.646112. 10.1007/s004930050062 · Checked 16 Oct 2026
  8. Mulmuley, K. (1999). Lower bounds in a parallel model without bit operations. SIAM Journal on Computing 28(4), 1460–1509. 10.1137/S0097539794282930 · Checked 16 Oct 2026
  9. Reingold, O. (2008). Undirected connectivity in log-space. Journal of the ACM 55(4), 17. 10.1145/1391289.1391291 · Checked 16 Oct 2026
  10. Svensson, O. & Tarnawski, J. (2017). The matching problem in general graphs is in quasi-NC. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 696–707. 10.1109/FOCS.2017.70 · Checked 16 Oct 2026
  11. Göös, M., Pitassi, T. & Watson, T. (2018). Deterministic communication vs. partition number. SIAM Journal on Computing 47(6), 2435–2450; conference version in FOCS 2015. 10.1137/16M1059369 · Checked 16 Oct 2026
  12. Fenner, S., Gurjar, R. & Thierauf, T. (2021). Bipartite perfect matching is in quasi-NC. SIAM Journal on Computing 50(3), STOC16-218–STOC16-235; published online 2019; conference version in STOC 2016. 10.1137/16M1097870 · Checked 16 Oct 2026
  13. de Rezende, S. F., Meir, O., Nordström, J., Pitassi, T. & Robere, R. (2024). KRW composition theorems via lifting. computational complexity 33(1), 4; conference version in FOCS 2020. 10.1007/s00037-024-00250-7 · Checked 16 Oct 2026
  14. Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 16 Oct 2026

Page reviewed 16 Oct 2026

Source

Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 08 Oct 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Computing