Sipser-Lautemann theorem

This article gives the statement, and proof, of one complexity class being contained in another one. The smaller complexity class is BPP and the larger complexity class is Sigma2P.

This article gives the statement, and proof, of one complexity class being contained in another one. The smaller complexity class is BPP and the larger complexity class is Pi2P.

This article gives the statement, and proof, of one complexity class being contained in another one. The smaller complexity class is BPP and the larger complexity class is Sigma2P intersect Pi2P.

Statement

Statement in terms of complexity classes

The theorem has the following equivalent forms:

1. The complexity class BPP is contained in the class ${\mathrm{\Sigma }}_{2}P$ (Sigma2P).
2. The complexity class BPP is contained in the class ${\mathrm{\Pi }}_{2}P$ (Pi2P).
3. The complexity class BPP is contained in the class ${\mathrm{\Sigma }}_{2}P\cap {\mathrm{\Pi }}_{2}P$ (Sigma2P intersect Pi2P).

Note that (1) and (2) are equivalent because BPP is self-complementary and ${\mathrm{\Sigma }}_2$ and ${\mathrm{\Pi }}_2$ are complements to each other. (3) implies both (1) and (2) and (1) and (2) together imply (3), so all statements are equivalent.