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:
“The custard is setting; meanwhile
I not only have my own history to worry about
But am forced to fret over insufficient details related to large
Unfinished concepts that can never bring themselves to the point
Of being, with or without my help, if any were forthcoming.”
—John Ashbery (b. 1927)
“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)
“Is a man too strong and fierce for society, and by temper and position a bad citizen,—a morose ruffian, with a dash of the pirate in him;Mnature sends him a troop of pretty sons and daughters, who are getting along in the dame’s classes at the village school, and love and fear for them smooths his grim scowl to courtesy. Thus she contrives to intenerate the granite and the feldspar, takes the boar out and puts the lamb in, and keeps her balance true.”
—Ralph Waldo Emerson (1803–1882)