<p>Suppose that every circuit of depth $C\log^{k+1} n$ and size $Dn^\ell$ can be converted to an equivalent circuit of depth $C'\log^k n$ and size $D' n^{\ell'}$.</p>

<p>Now suppose we are given a circuit of depth $C\log^{k+2} n$ and size $Dn^\ell$, and assume furthermore that it's a levelled circuit (making a circuit levelled only increases the size polynomially). Make a list of all nodes at levels $C\log^{k+1} n,2C\log^{k+1} n,\ldots,C\log^{k+2} n$. A node at level $\alpha C\log^{k+1} n$ is the value of a circuit of depth $C\log^{k+1} n$ and size at most $Dn^\ell$ whose leaves are nodes at level $(\alpha+1)C\log^{k+1}n$. We can replace each of these circuits by an equivalent circuit of depth $C'\log^k n$ and size $D' n^{\ell'}$. In total, the new circuit will have depth $C'\log^{k+1} n$ and size at most $DD' n^{\ell+\ell'}$. This shows that $NC^{k+1} = NC^k$ implies $NC^{k+2} = NC^{k+1}$.</p>

CC BY-SA 3.0
2014-04-25T05:56:56.287Z
2014-04-25T05:56:56.287Z
Yuval Filmus
<p>Jianer Chen's paper "Characterizing parallel hierarchies by reducibilities" Information Processing Letters 39(1991) 303-307 shows the theorem:</p>

<p>If $NC^{k+1} = NC^k$ then we have $NC = NC^k$</p>

<p>His proof is for uniform circuit classes. What is for non uniform classes? Does the result still hold?</p>

CC BY-SA 3.0
2014-04-25T04:26:00.820Z
For non-uniform classes the implication is trivially true.
domotorp
CC BY-SA 3.0
2014-04-25T04:29:28.477Z
Could you show the reason please? I am new to this field. Thanks.
Tian
<concurrency><hierarchy-theorems>
Non uniform NC-hierarchy collapse?
Tian
# Non uniform NC-hierarchy collapse?

(Asked by: username_0 on 2014-04-24)

Jianer Chen's paper "Characterizing parallel hierarchies by reducibilities" Information Processing Letters 39(1991) 303-307 shows the theorem:

If $NC^{k+1} = NC^k$ then we have $NC = NC^k$

His proof is for uniform circuit classes. What is for non uniform classes? Does the result still hold?

**Tags:** concurrency, hierarchy-theorems

> **Comments:**
> **username_1**: For non-uniform classes the implication is trivially true.  
> **username_0**: Could you show the reason please? I am new to this field. Thanks.  

---

## 1 answers

### Answer by username_2 on 2014-04-25. Score: 11 | Accepted answer

Suppose that every circuit of depth $C\log^{k+1} n$ and size $Dn^\ell$ can be converted to an equivalent circuit of depth $C'\log^k n$ and size $D' n^{\ell'}$.

Now suppose we are given a circuit of depth $C\log^{k+2} n$ and size $Dn^\ell$, and assume furthermore that it's a levelled circuit (making a circuit levelled only increases the size polynomially). Make a list of all nodes at levels $C\log^{k+1} n,2C\log^{k+1} n,\ldots,C\log^{k+2} n$. A node at level $\alpha C\log^{k+1} n$ is the value of a circuit of depth $C\log^{k+1} n$ and size at most $Dn^\ell$ whose leaves are nodes at level $(\alpha+1)C\log^{k+1}n$. We can replace each of these circuits by an equivalent circuit of depth $C'\log^k n$ and size $D' n^{\ell'}$. In total, the new circuit will have depth $C'\log^{k+1} n$ and size at most $DD' n^{\ell+\ell'}$. This shows that $NC^{k+1} = NC^k$ implies $NC^{k+2} = NC^{k+1}$.


---

