Questions: NC Class and Parallel Circuit Complexity

Question 1

An algorithm computes a result using O(n³) total operations (size), but is structured so that the computation can be completed in O(log² n) stages with unlimited processors. Which complexity class best describes this problem?

• A. P but not NC, because O(n³) operations exceeds the NC size bound
• B. NC^2, because the circuit has polylogarithmic depth (O(log² n)) and polynomial size (O(n³))
• C. NC^1, because the depth is polylogarithmic and that is the only criterion for NC^1
• D. Outside P, because having unlimited processors changes the model of computation entirely

Answer: (B)

NC^i consists of problems computable by polynomial-size, O(log^i n)-depth circuits. This algorithm uses O(n³) ≤ polynomial size and O(log² n) = O(log^2 n) depth — so it falls in NC^2 (the NC class indexed by log-squared depth). NC^1 requires O(log n) depth (not log² n), so option C is wrong. Option A incorrectly asserts O(n³) exceeds NC size bounds — NC requires polynomial size, and n³ is polynomial. Option D is wrong; the circuit model with unlimited parallelism is a standard computational model, and its relationship to P is the central question of the NC vs. P problem.

Question 2

Why does NC ⊆ P follow directly from the definitions of NC and P, without requiring any sophisticated proof?

• A. Because every NC algorithm can be converted to a polynomial-time Turing machine by evaluating the circuit gate by gate in topological order
• B. Because NC = P is currently believed to be true, and NC ⊆ P follows from the equality
• C. Because all polynomial-size circuits can be evaluated in logarithmic time on a sequential machine
• D. Because NC problems have low depth, and low depth implies low sequential time on any machine

Answer: (A)

A circuit of polynomial size S has at most S gates. Evaluating gates in topological order (inputs first, then gates whose inputs are already computed) takes at most S steps sequentially — one step per gate. Since S is polynomial, this sequential evaluation is polynomial-time. Therefore any NC circuit can be evaluated in polynomial time by a Turing machine. NC ⊆ P. Option B incorrectly states NC = P is believed true — in fact NC = P is open and likely false. Option C reverses the relationship: low depth allows fast *parallel* evaluation, not fast sequential evaluation. Option D is imprecise; depth alone doesn't bound sequential time — it's the size that matters for sequential simulation.

Question 3

In circuit complexity, a circuit's depth measures the total number of gates — the more gates, the deeper the circuit.

• T. True
• F. False

Answer: False

Depth and size are distinct resources. *Size* is the total number of gates in the circuit. *Depth* is the length of the longest path from any input to the output — it measures how many sequential computation steps are needed if all gates on the same level can compute in parallel. A circuit can have enormous size (millions of gates) but shallow depth if those gates can all operate in parallel. Conversely, a small circuit can have large depth if computations are chained sequentially. NC exploits this distinction: it demands polylogarithmic depth (fast parallel time) but allows polynomial size (large total work).

Question 4

The circuit value problem (CVP) — evaluating a Boolean circuit on a given input — is in NC, making it a natural benchmark for efficient parallelism.

• T. True
• F. False

Answer: False

CVP is P-complete, not in NC (under standard assumptions). This is the central irony noted in the topic: the very computational model used to define NC turns out to characterize what is believed to be outside NC. P-completeness means CVP is as hard as any problem in P under NC reductions — if CVP were in NC, then NC = P. CVP is P-complete because evaluating a circuit inherently requires following the computation gate by gate, and each gate's output may depend on the previous gate's output in ways that cannot be parallelized. This makes CVP the canonical example of a problem that appears inherently sequential.

Question 5

Explain why NC ⊆ P but the question of whether P ⊆ NC (equivalently, NC = P) remains open, using the relationship between circuit depth and sequential computation.

Model answer: NC ⊆ P because any NC circuit (polynomial size, polylogarithmic depth) can be evaluated sequentially in polynomial time by processing gates in topological order — polynomial size bounds the number of steps. The reverse direction P ⊆ NC would require showing that every polynomial-time algorithm can be restructured to use only polylogarithmic depth. The obstacle is that some P algorithms appear to be inherently sequential: each step depends on the result of the previous step in a chain that cannot be parallelized. P-complete problems like circuit value problem are believed to capture this sequential dependency — if any P-complete problem were in NC, all of P would be. The question remains open because we lack the tools to prove circuit lower bounds that would separate NC from P.

The NC = P question is the parallel analog of P vs. NP: it asks whether efficient sequential computation can always be efficiently parallelized. The intuition that the answer is 'no' (NC ≠ P) is strong — sequential algorithms with step-by-step dependency seem genuinely not parallelizable — but proving lower bounds on circuit depth remains technically elusive, just as proving P ≠ NP remains beyond current mathematics.