Editing BPP (complexity) (section)

== Problems ==
{{unsolved|computer science|{{tmath|1= \mathsf P \overset{?}{=} \mathsf{BPP} }}}}
All problems in '''P''' are obviously also in '''BPP'''. However, many problems have been 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 known to be in '''BPP''' but not known to be in '''P''' was the problem of [[primality test|determining]] whether a given number is [[prime number|prime]]. However, in the 2002 paper ''[[AKS primality test|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 '''[[RP (complexity)|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, when you have access to the value of the polynomial for any given input, but not to the coefficients. In other words, is there an assignment of values to the variables such that when a nonzero polynomial is evaluated on these values, 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.<ref>Madhu Sudan and Shien Jin Ong. Massachusetts Institute of Technology: 6.841/18.405J Advanced Complexity Theory: [http://people.csail.mit.edu/madhu/ST03/scribe/lect06.pdf Lecture 6: Randomized Algorithms, Properties of BPP]. February 26, 2003.</ref>