7
$\begingroup$

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?

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

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.