Complete Problems and Other Properties
Unlike BPP, PP is a syntactic, rather than semantic class. Any polynomial-time probabilistic machine recognizes some language in PP. In contrast, given a description of a polynomial-time probabilistic machine, it is undecidable in general to determine if it recognizes a language in BPP.
PP has natural complete problems, for example, MAJSAT. MAJSAT is a decision problem in which one is given a Boolean formula F. The answer must be YES if more than half of all assignments x1, x2, ..., xn make F true and NO otherwise.
Read more about this topic: PP (complexity)
Famous quotes containing the words complete, problems and/or properties:
“Reporters for tabloid newspapers beat a path to the park entrance each summer when the national convention of nudists is held, but the cult’s requirement that visitors disrobe is an obstacle to complete coverage of nudist news. Local residents interested in the nudist movement but as yet unwilling to affiliate make observations from rowboats in Great Egg Harbor River.”
—For the State of New Jersey, U.S. public relief program (1935-1943)
““What we know, is a point to what we do not know.” Open any recent journal of science, and weigh the problems suggested concerning Light, Heat, Electricity, Magnetism, Physiology, Geology, and judge whether the interest of natural science is likely to be soon exhausted.”
—Ralph Waldo Emerson (1803–1882)
“The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
—John Locke (1632–1704)