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:
“More than a decade after our fellow citizens began bedding down on the sidewalks, their problems continue to seem so intractable that we have begun to do psychologically what government has been incapable of doing programmatically. We bring the numbers down—not by solving the problem, but by deciding it’s their own damn fault.”
—Anna Quindlen (b. 1952)
“I was a wonderful parent before I had children. I was an expert on why everyone else was having problems with theirs. Then I had three of my own.”
—Adele Faber (20th century)
“We have heard all of our lives how, after the Civil War was over, the South went back to straighten itself out and make a living again. It was for many years a voiceless part of the government. The balance of power moved away from it—to the north and the east. The problems of the north and the east became the big problem of the country and nobody paid much attention to the economic unbalance the South had left as its only choice.”
—Lyndon Baines Johnson (1908–1973)