On properties of circuit for circuit evaluation as a parallelization procedure

AbstractIt 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