Rheinische Friedrich-Wilhelms-Universität Bonn 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


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

Powered by Zope