✦ LIBER ✦
Boolean complexity classes vs. their arithmetic analogs
✍ Scribed by Anna Gál; Avi Wigderson
- Book ID
- 102657146
- Publisher
- John Wiley and Sons
- Year
- 1996
- Tongue
- English
- Weight
- 719 KB
- Volume
- 9
- Category
- Article
- ISSN
- 1042-9832
No coin nor oath required. For personal study only.
✦ Synopsis
This paper provides logspace and small circuit depth analogs of the result of Valiant and Vazirani, which is a randomized (or nonuniform) reduction from N P to its arithmetic analog 6 3 P. We show a similar randomized reduction between the Boolean classes N L and semiunbounded fan-in Boolean circuits and their arithmetic counterparts. These reductions are based on the Isolation Lemma of Mulmuley, Vazirani. and Vazirani. Combinatorially our results can be viewed as simple (logspace) transformations of existential quantifiers into counting quantifiers in graphs and shallow circuits.