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)
“I’m no good at being noble, but it doesn’t take much to see that the problems of three little people don’t amount to a hill of beans in this crazy world. Someday you’ll understand that.”
—Julius J. Epstein, U.S. screenwriter, Philip Epstein, screenwriter, Howard Koch, screenwriter, and Michael Curtiz. Rick Blaine (Humphrey Bogart)
“A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.”
—Ralph Waldo Emerson (1803–1882)