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:
“Wittgenstein imagined that the philosopher was like a therapist whose task was to put problems finally to rest, and to cure us of being bewitched by them. So we are told to stop, to shut off lines of inquiry, not to find things puzzling nor to seek explanations. This is intellectual suicide.”
—Simon Blackburn (b. 1944)
“The problems of the world, AIDS, cancer, nuclear war, pollution, are, finally, no more solvable than the problem of a tree which has borne fruit: the apples are overripe and they are fallingwhat can be done?... Nothing can be done, and nothing needs to be done. Something is being donethe organism is preparing to rest.”
—David Mamet (b. 1947)
“I conceive that the leading characteristic of the nineteenth century has been the rapid growth of the scientific spirit, the consequent application of scientific methods of investigation to all the problems with which the human mind is occupied, and the correlative rejection of traditional beliefs which have proved their incompetence to bear such investigation.”
—Thomas Henry Huxley (182595)