28.11.2008

We prove that probabilistic NC¹ (PrNC¹) circuits (i.e. uniform log-depth poly-size circuits with unbounded error probability) are computationally exactly as powerful as probabilistic polynomial time. This entails that the probabilistic NC^k-hierarchy collapses at the NC¹ level; if unbounded fan-in is allowed it collapses even at the level 0. As a side effect we prove the identity PrNC = Pr₂SC = Pr₂SC¹ (Pr₂SC^k meaning simultaneous polynomial time and log^k n space bounded machines with two-way random tape [KV 84]). The central problems in computational complexity theory are whether NC = P [Co 83], NC² = NC and SC = NC [Co 79, Ru 81] and the most classical problem whether LOGSPACE = P. Surprisingly the results of the present paper and [KV 84] give affirmative answer to all these questions in the probabilistic case.