
University of Bonn > Department of Computer Science > Chair V  
CSReports 19851989  Copyright 19851989 University of Bonn, Department of Computer Science, Abt. V  
851 28.11.2008 
Probabilistic NC^{1}Circuits Equal Probabilistic Polynomial Time
Marek Karpinski and Rutger Verbeek [Download PostScript] [Download PDF] We prove that probabilistic NC^{1} (PrNC^{1}) circuits (i.e. uniform logdepth polysize 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^{1} level; if unbounded fanin is allowed it collapses even at the level 0. As a side effect we prove the identity PrNC = Pr_{2}SC = Pr_{2}SC^{1} (Pr_{2}SC^{k} meaning simultaneous polynomial time and log^{k} n space bounded machines with twoway random tape [KV 84]). The central problems in computational complexity theory are whether NC = P [Co 83], NC^{2} = 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
Deutsch 
University of Bonn > Department of Computer Science > Chair V 