PP is closed under intersection. (English) Zbl 0827.68040

Beigel, Richard; Reingold, Nick; Spielman, Daniel

J. Comput. Syst. Sci. 50, No. 2, 191-202 (1995).

Summary: In this 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 that are needed to compute the parity function.

MSC:

68Q05

Models of computation (Turing machines, etc.) (MSC2010)

Keywords:

probabilistic Turing machines