Vipul: Created page with "{{complexity class containment|smaller = BPP|larger = Sigma2P}} {{complexity class containment|smaller = BPP|larger = Pi2P}} {{complexity class containment|smaller = BPP|larger =..."

2010-08-13T00:43:50Z

Created page with "{{complexity class containment|smaller = BPP|larger = Sigma2P}} {{complexity class containment|smaller = BPP|larger = Pi2P}} {{complexity class containment|smaller = BPP|larger =..."

New page

{{complexity class containment|smaller = BPP|larger = Sigma2P}}
{{complexity class containment|smaller = BPP|larger = Pi2P}}
{{complexity class containment|smaller = BPP|larger = Sigma2P intersect Pi2P}}

==Statement==

===Statement in terms of complexity classes===

The theorem has the following equivalent forms:

# The complexity class [[BPP]] is contained in the class <math>\Sigma_2P</math> ([[Sigma2P]]).
# The complexity class [[BPP]] is contained in the class <math>\Pi_2P</math> ([[Pi2P]]).
# The complexity class [[BPP]] is contained in the class <math>\Sigma_2P \cap \Pi_2P</math> ([[Sigma2P intersect Pi2P]]).

Note that (1) and (2) are equivalent because [[BPP is self-complementary]] and <math>\Sigma_2</math> and <math>\Pi_2</math> are [[complementary complexity classes|complement]]s to each other. (3) implies both (1) and (2) and (1) and (2) together imply (3), so all statements are equivalent.

Sipser-Lautemann theorem - Revision history

Vipul: Created page with "{{complexity class containment|smaller = BPP|larger = Sigma2P}} {{complexity class containment|smaller = BPP|larger = Pi2P}} {{complexity class containment|smaller = BPP|larger =..."