PP (probabilistic polynomial time) was first studied in the 1970s, and basic properties of the class have been known since then (for instance, NP ⊆ PP, and PP is closed under complement). It had remained an open question whether PP is closed under intersection and union, and the popular conjecture held that the answer was “no.”

As the title indicates, this paper disproves the popular conjecture. The authors also prove closure under more general reductions; further progress is reported by Fortnow and Reingold [1].

Much has been learned about PP recently, beginning with Toda’s theorem showing that P^PP contains the polynomial hierarchy [2]. These results have also shed light on the power of threshold circuits, due to the similarity between PP machines (computing the majority vote of many computation paths) and majority gates. Thus, in this paper, the techniques developed are used to show how to reduce the number of threshold gates in a circuit.

The main technique involves constructing rational functions that express intersection in a sense, and then showing that PP machines can simulate these rational functions. This extends classical work on the expressive power of rational functions. This technique is a useful tool in understanding threshold circuits; anyone working in this area will need to become familiar with it.

The paper is well written. The results are important and surprising. Although many proofs are omitted in this conference version, it is not difficult for people working in this area to provide the missing details.