PP is closed under intersection

Authors: Richard Beigel, Nick Reingold, and Daniel A. Spielman.

Bibliographic Information: First appeared in the Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing, 1991, pp. 1-9. Will appear soon in the Journal of Computer and System Sciences.

Abstract

In his seminal paper on probabilistic Turing machines, Gill asked whether the class $\PP$ is closed under intersection and union. We give a positive answer to this question. We also show that $\PP$ is closed under a variety of polynomial-time truth-table reductions. Consequences in complexity theory include the definite collapse and (assuming $\P \neq \PP $) separation of certain query hierarchies over $\PP$.

Similar techniques allow us to combine several threshold gates into a single threshold gate. Consequences in the study of circuits include the simulation of circuits with a small number of threshold gates by circuits having only a single threshold gate at the root (perceptrons), and a lower bound on the number of threshold gates needed to compute the parity function.

To view the paper, click here.

To download a compressed version, click here.

Daniel A. Spielman

Last modified: Fri Aug 3 02:13:53 EDT 2001