On properties of circuit for circuit evaluation as a parallelization procedure

It is shown here that if NC = P , the NC hierarchy collapses. We give two proofs for this. From the point of view of a circuit for circuit evaluation, the assumption that NC = P implies that any polynomial size circuit can be transduced into a polynomial size and poly‐log depth circuit. Such a parallelization property can be applied not only for uniform circuits but also for nonuniform circuits. This interesting property suggests that the assumption NC = P would be false. © 2007 Wiley Periodicals, Inc. Electr Eng Jpn, 162(2): 46–50, 2008; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/eej.20488