Problems
| Is P = BPP ? |
Besides the problems in P, which are obviously in BPP, many problems were known to be in BPP but not known to be in P. The number of such problems is decreasing, and it is conjectured that P = BPP.
For a long time, one of the most famous problems that was known to be in BPP but not known to be in P was the problem of determining whether a given number is prime. However, in the 2002 paper PRIMES is in P, Manindra Agrawal and his students Neeraj Kayal and Nitin Saxena found a deterministic polynomial-time algorithm for this problem, thus showing that it is in P.
An important example of a problem in BPP (in fact in co-RP) still not known to be in P is polynomial identity testing, the problem of determining whether a polynomial is identically equal to the zero polynomial. In other words, is there an assignment of variables such that when the polynomial is evaluated the result is nonzero? It suffices to choose each variable's value uniformly at random from a finite subset of at least d values to achieve bounded error probability, where d is the total degree of the polynomial.
Read more about this topic: BPP (complexity)
Famous quotes containing the word problems:
“I rarely speak about God. To God, yes. I protest against Him. I shout at Him. But to open a discourse about the qualities of God, about the problems that God imposes, theodicy, no. And yet He is there, in silence, in filigree.”
—Elie Wiesel (b. 1928)
“While the onset of puberty can vary by as much as six years, every adolescent wants to be right on the 50-yard line, right in the middle of the field. One is always too tall, too short, too thin, too fat, too hairy, too clear-skinned, too early, too late. Understandably, problems of self-image are rampant.”
—Joan Lipsitz (20th century)
“As our disorderly, competitive technological society is piling up its victims and constantly developing new problems of maladjustment, we must use our scientific knowledge to determine the cause and prevention of suffering rather than putting all our emphasis on its alleviation ...”
—Agnes E. Meyer (1887–1970)