<p>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.</p>

CC BY-SA 4.0
2024-07-07T18:50:31.943Z
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.
Hlkwtz
CC BY-SA 4.0
2024-07-06T20:04:24.240Z
2024-07-06T20:04:24.240Z
mic
<p>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 &quot;slice&quot; 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.</p>

CC BY-SA 4.0
2024-07-09T19:24:06.240Z
2024-07-09T19:24:06.240Z
Eric Allender
<p>Im looking at the proof of <span class="math-container">$NC^{i} = NC^{i+1} \implies NC = NC^i,\,i\geq 1$</span> in page 10 of the following article: <a href="https://www.cs.uoregon.edu/Reports/TR-1986-001.pdf" rel="nofollow noreferrer">https://www.cs.uoregon.edu/Reports/TR-1986-001.pdf</a>
<br />
<br />
I understand the general idea consists in creating a family of uniform circuits of depth <span class="math-container">$O(log^{i+1}n)$</span> from a circuit of depth <span class="math-container">$O(log^{i+2}n)$</span>, please correct me if im wrong. However, I lose track of whats going on when it mentions that transitive closure is in <span class="math-container">$NC^2$</span>, I don't understand the use of this problem in this proof, and again, maybe thats because im missing the bigger picture.</p>

<cc.complexity-theory><complexity-classes><circuit-complexity><hierarchy-theorems>
Use of transitive closure in proof of NC hierarchy collapse
Hlkwtz
# Use of transitive closure in proof of NC hierarchy collapse

(Asked by: username_0 on 2024-07-04)

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.

**Tags:** cc.complexity-theory, complexity-classes, circuit-complexity, hierarchy-theorems

---

## 2 answers

### Answer by username_1 on 2024-07-06. Score: 2

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.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_2 on 2024-07-09. Score: 2

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.


---

