The complexity class BPP: Difference between revisions
No edit summary |
|||
| (2 intermediate revisions by one other user not shown) | |||
| Line 4: | Line 4: | ||
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 a majority vote to determine the answer, the chance of making an error decreases exponentially with the number of times the algorithm is run. | 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 a majority vote to determine the answer, the chance of making an error decreases exponentially with the number of times the algorithm is run. | ||
Many randomized algorithms are less symmetrical than this, and have the property that if f(x)=1 then the algorithm outputs 1 with probability 1-c for some small c, but if f(x)=0, then it outputs 0 with probability 1. This class of problems is called RP. As above, for defining the complexity class one can take c to be some constant like 1/2, since one can always improve the probability by running the algorithm several times. The class co-RP consists of problems where the opposite holds: if f(x)=1 then the algorithm always outputs 1 and if f(x)=0 then it outputs 0 with high probability. | |||
== 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. 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. | 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 with the number of points, and so if it vanishes at all those points we can say with some confidence that the polynomial vanishes everywhere. This problem is also in co-RP, since if the polynomial really does vanish everywhere, then the algorithm is guaranteed to output 1. | ||
''It would be good to have more examples. In particular, it would be nice to have an example that isn't obviously in RP or co-RP.'' | |||
Latest revision as of 08:28, 29 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]\displaystyle{ 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 a majority vote to determine the answer, the chance of making an error decreases exponentially with the number of times the algorithm is run.
Many randomized algorithms are less symmetrical than this, and have the property that if f(x)=1 then the algorithm outputs 1 with probability 1-c for some small c, but if f(x)=0, then it outputs 0 with probability 1. This class of problems is called RP. As above, for defining the complexity class one can take c to be some constant like 1/2, since one can always improve the probability by running the algorithm several times. The class co-RP consists of problems where the opposite holds: if f(x)=1 then the algorithm always outputs 1 and if f(x)=0 then it outputs 0 with high probability.
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 with the number of points, and so if it vanishes at all those points we can say with some confidence that the polynomial vanishes everywhere. This problem is also in co-RP, since if the polynomial really does vanish everywhere, then the algorithm is guaranteed to output 1.
It would be good to have more examples. In particular, it would be nice to have an example that isn't obviously in RP or co-RP.
