Im looking at the proof of $NC^{i} = NC^{i+1} \implies NC = NC^i,\,i\geq 1$ in page 10 of the following article: https://www.cs.uoregon.edu/Reports/TR-1986-001.pdf
I understand the general idea consists in creating a family of uniform circuits of depth $O(log^{i+1}n)$ from a circuit of depth $O(log^{i+2}n)$, please correct me if im wrong. However, I lose track of whats going on when it mentions that transitive closure is in $NC^2$, I don't understand the use of this problem in this proof, and again, maybe thats because im missing the bigger picture.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
The issue may be that the uniform circuit description is not leveled, you just see gates and wires. But using TC, you can compute a level number for every gate.
-
$\begingroup$ So basically when we divide the bigger circuit we get a circuit mess and this is allowing us to order it into the corresponding levels? In that case I still cant visualize the whole process involving the use of TC. $\endgroup$– HlkwtzCommented Jul 7 at 18:50
$\begingroup$
$\endgroup$
The answer by Mic is correct. If you're not comfortable thinking of this in terms of Transitive Closure, instead use the fact that NL is in NC^2. In NL, it is easy to determine the depth of each gate in a uniform family of circuits. Thus, by the assumption that NC^{k+1} is equal to NC^k, there is an NC^k circuit family that takes x as input, and outputs a sequence of j=O(log n) circuits C_1, ... C_j, where each C_i is a subcircuit of our original circuit (of depth log^{k+2}n), corresponding to the i'th "slice" of depth log^{k+1}n. That is, C_1 is the slice of the original circuit closest to the inputs, and the outputs of C_1 feed into the gates of C_2, etc. By assumption, each of the C_i's (of depth log^{k+1}) can be replaced by uniform circuits of depth O(log^k n). Gluing these circuits together gives a circuit of depth O(log^{k+1}n) ... which by assumption gives a language in NC^k.
