Department of Computer Science
Chair V

University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1985-1989 Copyright 1985-1989 University of Bonn, Department of Computer Science, Abt. V


Probabilistic NC1-Circuits Equal Probabilistic Polynomial Time
Marek Karpinski and Rutger Verbeek
[Download PostScript] [Download PDF]

We prove that probabilistic NC1 (PrNC1) 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 NCk-hierarchy collapses at the NC1 level; if unbounded fan-in is allowed it collapses even at the level 0. As a side effect we prove the identity PrNC = Pr2SC = Pr2SC1 (Pr2SCk meaning simultaneous polynomial time and logk n space bounded machines with two-way random tape [KV 84]). The central problems in computational complexity theory are whether NC = P [Co 83], NC2 = 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.

Last Change: 11/28/08 at 13:14:42
University of Bonn -> Department of Computer Science -> Chair V