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:
“If family communication is good, parents can pick up the signs of stress in children and talk about it before it results in some crisis. If family communication is bad, not only will parents be insensitive to potential crises, but the poor communication will contribute to problems in the family.”
—Donald C. Medeiros (20th century)
“Sustained unemployment not only denies parents the opportunity to meet the food, clothing, and shelter needs of their children but also denies them the sense of adequacy, belonging, and worth which being able to do so provides. This increases the likelihood of family problems and decreases the chances of many children to be adequately prepared for school.”
—James P. Comer (20th century)
“If when a businessman speaks of minority employment, or air pollution, or poverty, he speaks in the language of a certified public accountant analyzing a corporate balance sheet, who is to know that he understands the human problems behind the statistical ones? If the businessman would stop talking like a computer printout or a page from the corporate annual report, other people would stop thinking he had a cash register for a heart. It is as simple as that—but that isn’t simple.”
—Louis B. Lundborg (1906–1981)