PP (complexity) - Complete Problems and Other Properties

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:

    Let’s holler and ask him if he won’t prescribe
    For all humanity a complete rest
    From all this wagery. But what’s the use
    Of asking any sympathy of him?
    That class of people don’t know what work is....
    Robert Frost (1874–1963)

    I was a wonderful parent before I had children. I was an expert on why everyone else was having problems with theirs. Then I had three of my own.
    Adele Faber (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)