Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1985-1989 Copyright 1985-1989 Universität Bonn, Institut für Informatik, Abt. V
851

28.11.2008

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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V