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:
“The Settlement ... is an experimental effort to aid in the solution of the social and industrial problems which are engendered by the modern conditions of life in a great city. It insists that these problems are not confined to any one portion of the city. It is an attempt to relieve, at the same time, the overaccumulation at one end of society and the destitution at the other ...”
—Jane Addams (1860–1935)
“If we parents accept that problems are an essential part of life’s challenges, rather than reacting to every problem as if something has gone wrong with universe that’s supposed to be perfect, we can demonstrate serenity and confidence in problem solving for our kids....By telling them that we know they have a problem and we know they can solve it, we can pass on a realistic attitude as well as empower our children with self-confidence and a sense of their own worth.”
—Barbara Coloroso (20th century)
“One of the annoying things about believing in free will and individual responsibility is the difficulty of finding somebody to blame your problems on. And when you do find somebody, it’s remarkable how often his picture turns up on your driver’s license.”
—P.J. (Patrick Jake)