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:
“A complete woman is probably not a very admirable creature. She is manipulative, uses other people to get her own way, and works within whatever system she is in.”
—Anita Brookner (b. 1938)
“All problems are finally scientific problems.”
—George Bernard Shaw (1856–1950)
“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)