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:
“In the middle years of childhood, it is more important to keep alive and glowing the interest in finding out and to support this interest with skills and techniques related to the process of finding out than to specify any particular piece of subject matter as inviolate.”
—Dorothy H. Cohen (20th century)
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)
“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)