NC versus P
Can every problem solvable in polynomial time be solved in polylogarithmic time on a parallel computer with polynomially many processors?
Summary
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
- 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]?
- 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]?
- 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].
- 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]?
- 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]?
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Reingold, O. (2008). Undirected connectivity in log-space. Journal of the ACM 55(4), 17. 10.1145/1391289.1391291 · Checked 16 Oct 2026
- 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
- 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
- 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
- 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
- Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 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.