Related Complexity Classes
The definition of RP says that a YES answer is always right and that a NO answer is usually right. The complexity class co-RP is similarly defined, except that NO is always right and YES is usually right. In other words, it accepts all YES instances but can either accept or reject NO instances. The class BPP describes algorithms that can give incorrect answers on both YES and NO instances, and thus contains both RP and co-RP. The intersection of the sets RP and co-RP is called ZPP. Just as RP may be called R, some authors use the name co-R rather than co-RP.
Read more about this topic: RP (complexity)
Famous quotes containing the words related, complexity and/or classes:
“Generally there is no consistent evidence of significant differences in school achievement between children of working and nonworking mothers, but differences that do appear are often related to maternal satisfaction with her chosen role, and the quality of substitute care.”
—Ruth E. Zambrana, U.S. researcher, M. Hurst, and R.L. Hite. “The Working Mother in Contemporary Perspectives: A Review of Literature,” Pediatrics (December 1979)
“The price we pay for the complexity of life is too high. When you think of all the effort you have to put in—telephonic, technological and relational—to alter even the slightest bit of behaviour in this strange world we call social life, you are left pining for the straightforwardness of primitive peoples and their physical work.”
—Jean Baudrillard (b. 1929)
“I have no doubt but that the misery of the lower classes will be found to abate whenever the Government assumes a freer aspect and the laws favor a subdivision of Property.”
—James Madison (1751–1836)