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:
“Man finds nothing so intolerable as to be in a state of complete rest, without passions, without occupation, without diversion, without effort. Then he feels his nullity, loneliness, inadequacy, dependence, helplessness, emptiness.”
—Blaise Pascal (1623–1662)
“If family communication is good, parents can pick up the signs of stress in children and talk about it before it results in some crisis. If family communication is bad, not only will parents be insensitive to potential crises, but the poor communication will contribute to problems in the family.”
—Donald C. Medeiros (20th century)
“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)