BOOLEAN COMPLEXITY CLASSES VS THEIR ARITHMETIC ANALOGS

This paper provides logspace and small circuit depth analogs of the re sult of Valiant and Vazirani, which is a randomized (or nonuniform) re duction from NP to its arithmetic analog circle plus P. We show a simi lar randomized reduction between the Boolean classes NL and semiunboun ded fan-in Boolean circuits and their arithmetic counterparts. These r eductions are based on the Isolation Lemma of Mulmuley, Vazirani, and Vazirani. Combinatorially our results can be viewed as simple (logspac e) transformations of existential quantifiers into counting quantifier s in graphs and shallow circuits. (C) 1996 John Wiley & Sons, Inc.