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:
“There is nothing but is related to us, nothing that does not interest us,—kingdom, college, tree, horse, or iron show,—the roots of all things are in man.”
—Ralph Waldo Emerson (1803–1882)
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)
“Solidity, caution, integrity, efficiency. Lack of imagination, hypocrisy. These qualities characterize the middle classes in every country, but in England they are national characteristics.”
—E.M. (Edward Morgan)