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:
“Down these mean streets a man must go who is not himself mean, who is neither tarnished nor afraid.... He is the hero, he is everything. He must be a complete man and a common man and yet an unusual man. He must be, to use a rather weathered phrase, a man of honor, by instinct, by inevitability, without thought of it, and certainly without saying it. He must be the best man in his world and a good enough man for any world.”
—Raymond Chandler (1888–1959)
“Currently, U.S. society has been encouraged by its political and subsidized mass-media intelligentsia to view U.S. life as a continual “morning in America” paradise, where the only social problems occur in the inner cities. Psychologists call this denial.”
—Ishmael Reed (b. 1938)
“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)