# Non uniform NC-hierarchy collapse?

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?

• For non-uniform classes the implication is trivially true. Apr 25 '14 at 4:26
• Could you show the reason please? I am new to this field. Thanks.
– Tian
Apr 25 '14 at 4:29

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}$.