P versus NC

Can every efficiently solvable yes-or-no problem be reorganized into a small number of parallel stages? To check whether eight input bits are all 1, a chain can combine them one after another in seven stages. A tree instead combines four pairs at once, then two pairs of results, then the final pair: three stages, still seven operations. The family P allows deterministic algorithms whose step count is bounded by a fixed power of input length. The parallel family NC keeps a fixed-power bound on total work, but its stage count grows only like a fixed power of the number of digits needed to write that length. Each operation has a fixed bound on its number of inputs. An algorithm must generate the plans using working memory that grows only like that digit count. Is every problem in P also in NC?[1]

Can every yes-or-no problem solved without random choices, in a number of sequential steps bounded by a fixed power of input length, also be solved with a fixed-power amount of total work and very few parallel stages? The sequential family is called P. The unknown is whether efficient decisions can require sequential dependence even after their algorithms are redesigned.

A Boolean circuit uses gates such as AND, OR and NOT. Its size counts gates; its depth counts the longest chain of dependent gates. For eight input bits, combining one new bit at a time gives an AND circuit with seven gates and depth seven. A balanced tree has the same seven gates and depth three. This checked example shows that a slow schedule can sometimes be replaced; it does not prove that every task can be.

Each gate may read at most a fixed number of earlier values; this is bounded fan-in. For n input bits, NC also requires polynomial size, meaning a fixed-power bound, and depth $O((\log n)^k)$ for some fixed integer $k\ge1$. It requires logspace uniformity: a deterministic algorithm generates the circuit for each input length using $O(\log n)$ working space. Thus a different precomputed circuit cannot secretly contain unrestricted advice for each length. The question is whether $\mathrm{NC}=\mathrm{P}$, given the known inclusion $\mathrm{NC}\subseteq\mathrm{P}$.[1]

We do not know whether all of P can be parallelized with the NC bounds.[1] [2]

Parallel algorithms for selected languages do not establish equality. No unconditional separation of these classes is known.[1] [2]

More processors help when work can be done independently; they cannot make a needed earlier answer available sooner just by waiting in parallel. This question asks whether such dependence is sometimes unavoidable even after changing the whole algorithm, setting a limit on what parallel computation could achieve.[1]

Evaluating an arbitrary supplied Boolean circuit is a concrete representative of the difficulty. The circuit and its input bits are both given, and the task is to compute its output bit. This is P-complete under reductions compatible with NC: every polynomial-time decision can be translated efficiently into such an instance. An NC algorithm for this one task would therefore imply P equals NC. The issue is the waiting imposed by general dependencies, rather than the mere presence of many gates.[1]