Difference between revisions of "The complexity class BPP"

From Polymath Wiki
Jump to: navigation, search
Line 3: Line 3:
 
The complexity class BPP is, very roughly, the class of all problems for which there is a randomized algorithm that runs in polynomial time and almost always gives the right answer.  
 
The complexity class BPP is, very roughly, the class of all problems for which there is a randomized algorithm that runs in polynomial time and almost always gives the right answer.  
  
A slightly more formal definition is the following. A Boolean function <math>f:\bigcup_{n=1}^\infty\{0,1\}^n\rightarrow\{0,1\}</math> belongs to BPP if there is a randomized polynomial-time algorithm such that for any x such that f(x)=1 it will output 1 with probability at least 2/3, and for any x such that f(x)=0 it will output 0 with probability at least 2/3. This may not sound like "almost always" getting the right answer, but a standard trick allows you to get the almost always from such an algorithm: you just run it several times. If there is a probability of 2/3 of getting the answer right, then almost certainly you will get the answer right over half the time if you run the algorithm (independently) 50 times, say. Indeed, the probability that this is not the case decreases exponentially with the number of times you repeat the algorithm.  
+
A slightly more formal definition is the following. A Boolean function <math>f:\bigcup_{n=1}^\infty\{0,1\}^n\rightarrow\{0,1\}</math> belongs to BPP if there is a randomized polynomial-time algorithm such that for any x such that f(x)=1 it will output 1 with probability at least 2/3, and for any x such that f(x)=0 it will output 0 with probability at least 2/3. This may not sound like "almost always" getting the right answer, but if you run the algorithm repeatedly and take the majority vote, the chance of making an error decreases exponentially with the number of times you run the algorithm.  
  
 
== Examples ==
 
== Examples ==
  
The problem of determining whether a [http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma_and_testing_polynomial_identities multivariate polynomial vanishes] is in BPP.  The idea of the randomized algorithm is to compute the polynomial at a small number of randomly chosen points.  If it vanishes at all those points, then we can say with some confidence that the polynomial vanishes.  This probability increases rapidly as the number of points increases.
+
The problem of determining whether a [http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma_and_testing_polynomial_identities multivariate polynomial vanishes] is in BPP.  The idea of the randomized algorithm is to compute the polynomial at a small number of randomly chosen points.  For a non-zero polynomial the probability that it vanishes at all those points decreases rapidly, and so if it vanishes at all those points we can say with some confidence that the polynomial vanishes.

Revision as of 22:54, 28 July 2009

Definition

The complexity class BPP is, very roughly, the class of all problems for which there is a randomized algorithm that runs in polynomial time and almost always gives the right answer.

A slightly more formal definition is the following. A Boolean function [math]f:\bigcup_{n=1}^\infty\{0,1\}^n\rightarrow\{0,1\}[/math] belongs to BPP if there is a randomized polynomial-time algorithm such that for any x such that f(x)=1 it will output 1 with probability at least 2/3, and for any x such that f(x)=0 it will output 0 with probability at least 2/3. This may not sound like "almost always" getting the right answer, but if you run the algorithm repeatedly and take the majority vote, the chance of making an error decreases exponentially with the number of times you run the algorithm.

Examples

The problem of determining whether a multivariate polynomial vanishes is in BPP. The idea of the randomized algorithm is to compute the polynomial at a small number of randomly chosen points. For a non-zero polynomial the probability that it vanishes at all those points decreases rapidly, and so if it vanishes at all those points we can say with some confidence that the polynomial vanishes.