[Computational Complexity] How Many Sides to Your Error?
- I often get asked various questions about complexity but I now had the same question asked twenty years apart.
Are there natural problems in BPP not known to be in RP∪co-RP?Informally the class of BPP are the problems efficiently computable on a probabilistic computer with a very small chance of error. For RP if the program says "Yes" it is always right. For co-RP, if the program says "No" it is always right. The questions asks if there are any natural problems that have probabilistic algorithms that seem to require error on both the Yes and No answers.
In the late 80's, David Johnson asked me (and several others) the question when he was putting together his Catalog of Complexity Classes for the Handbook. I didn't have any examples and his catalog ended up citing the 1984 work of Bach, Miller and Shallit offering up Perfect Numbers (and some variants) an an answer to the question. But Bach et. al made their argument based on the fact that the current primality tests put Primes in co-RP but not in RP. In 1987, Adleman and Huang (building on Goldwasser and Kilian) put Primes in RP too. This puts Perfect Numbers in RP killing that example a few years before the Handbook appeared.
Since Primes were put in P in 2002, we have so few problems even known to be in BPP but not in P with the best remaining example the co-RP problem of determining whether two algebraic circuits are identical. So we still don't have any good answers to the above question except for some contrived problems like given three algebraic circuits, are exactly two of them identical. Most complexity theorists believe we have strong enough pseudorandom generators to avoid the randomness in probabilistic algorithms altogether. So in the end the question is likely irrelevant. Still we complexity theorists also like to know what we can prove beyond what we just believe.
All this doesn't mean BPP is not the right class to capture probabilistic algorithms when you can trust your randomness and don't mind a negligible error on either side. Complexity classes are defined to capture the properties we want them to have, not to mold to our limited knowledge of current problems.
Posted By Lance to Computational Complexity at 12/02/2008 06:42:00 AM