BPP - Revision history

Vipul: /* Smaller complexity classes */

2011-12-27T20:37:20Z

Smaller complexity classes

← Older revision		Revision as of 20:37, 27 December 2011
Line 42:		Line 42:
	\| [[Contains::P]] \|\| deterministic polynomial time \|\| [[P is in BPP]] \|\| open -- see [[P equals BPP conjecture]] \|\| {{intermediate complexity classes\|P\|BPP}}		\| [[Contains::P]] \|\| deterministic polynomial time \|\| [[P is in BPP]] \|\| open -- see [[P equals BPP conjecture]] \|\| {{intermediate complexity classes\|P\|BPP}}
	\|}		\|}

			==Properties==

	{\| class="sortable" border="1"		{\| class="sortable" border="1"

Vipul: /* Smaller complexity classes */

2011-12-27T20:36:55Z

Smaller complexity classes

@@ Line 41: / Line 41: @@
 |-
 | [[Contains::P]] || deterministic polynomial time || [[P is in BPP]] || open -- see [[P equals BPP conjecture]] || {{intermediate complexity classes|P|BPP}}
 |}

Vipul at 00:25, 13 August 2010

2010-08-13T00:25:40Z

← Older revision		Revision as of 00:25, 13 August 2010
Line 4:		Line 4:

	'''BPP''' or '''bounded-error probabilistic polynomial time''' is a complexity class that can loosely be described as the class of languages in which membership can be decided using a randomized algorithm that runs in polynomial time, with the probability of error either way bounded by a number less than <math>1/2</math>.		'''BPP''' or '''bounded-error probabilistic polynomial time''' is a complexity class that can loosely be described as the class of languages in which membership can be decided using a randomized algorithm that runs in polynomial time, with the probability of error either way bounded by a number less than <math>1/2</math>.

			===Using <math>2/3</math> and <math>1/3</math>===

			More formally, a language <math>L</math> is in BPP if there exist functions <math>f</math> and <math>g</math> growing polynomially in their inputs, such that for any string of length <math>n</math>, the algorithm uses the string and a random string of length <math>f(n)</math> to output, in time at most <math>g(n)</math>, whether the string is in <math>L</math>, and the answer satisfies the following: For ''every'' choice of input string, less than <math>1/3</math> of the possible random strings of length <math>f(n)</math> give the wrong answer.

			Note that the probability is taken over the random string and ''not'' over the input string. For the input string, we are interested in the ''worst case'' probability, i.e., we would like a low error probability for ''all'' input strings.

	==Relation with other complexity classes==		==Relation with other complexity classes==

Vipul: Created page with "{{complexity class}} ==Definition== '''BPP''' or '''bounded-error probabilistic polynomial time''' is a complexity class that can loosely be described as the class of languages..."

2010-08-13T00:16:46Z

Created page with "{{complexity class}} ==Definition== '''BPP''' or '''bounded-error probabilistic polynomial time''' is a complexity class that can loosely be described as the class of languages..."

New page

{{complexity class}}

==Definition==

'''BPP''' or '''bounded-error probabilistic polynomial time''' is a complexity class that can loosely be described as the class of languages in which membership can be decided using a randomized algorithm that runs in polynomial time, with the probability of error either way bounded by a number less than <math>1/2</math>.

==Relation with other complexity classes==

===Larger complexity classes===

{| class="sortable" border="1"
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes
|-
| [[Contained in::PP]] || probabilistic polynomial time; like BPP but probability of giving the correct output is allowed to equal <math>1/2</math> || [[PP contains BPP]] || ||
|-
| [[Contained in::P/poly]] || For any fixed input length, there is a polynomial sized advice string depending on the length, using which a polynomial time algorithm can be devised for all inputs of that length. || [[Adleman's theorem]] || Separated: [[P/poly contains undecidable languages]] || {{intermediate complexity classes|BPP|P/poly}}
|-
| [[Contained in::Sigma2P]] || <math>\Sigma_2</math> in the polynomial hierarchy || part of the [[Sipser-Lautemann theorem]] || open, but if true, would imply that [[NP]] is in [[P/poly]] and hence PH collapses to BPP || {{intermediate complexity classes|BPP|Sigma2P}}
|-
| [[Contained in::Pi2P]] || <math>\Pi_2</math> in the polynomial hierarchy || part of the [[Sipser-Lautemann theorem]] || open, but if true, would imply that [[NP]] is in [[P/poly]] and hence PH collapses to BPP || {{intermediate complexity classes|BPP|Pi2P}}
|-
| [[Contained in::Sigma2P intersect Pi2P]] || <math>\Sigma_2P \cap \Pi_2P</math> || [[Sipser-Lautemann theorem]] || open, but if true, would imply that [[NP]] is in [[P/poly]] and hence PH collapses to BPP || {{intermediate complexity classes|BPP|Sigma2P intersect Pi2P}}
|-
| [[Contained in::PH]] || The union of the entire polynomial hierarchy || (via Sigma2P) || open || {{intermediate complexity classes|BPP|PH}}
|}

===Smaller complexity classes===

{| class="sortable" border="1"
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes
|-
| [[Contains::RP]] || randomized polynomial time -- no false positives, but possible false negatives || [[RP is in BPP]] || open||{{intermediate complexity classes|RP|BPP}}
|-
| [[Contains::co-RP]] || randomized polynomial time -- no false negatives, but possible false positives || [[co-RP is in BPP]] || open || {{intermediate complexity classes|co-RP|BPP}}
|-
| [[Contains::P]] || deterministic polynomial time || [[P is in BPP]] || open -- see [[P equals BPP conjecture]] || {{intermediate complexity classes|P|BPP}}
|}