Definition
A language L is in PP if and only if there exists a probabilistic Turing machine M, such that
- M runs for polynomial time on all inputs
- For all x in L, M outputs 1 with probability strictly greater than 1/2
- For all x not in L, M outputs 1 with probability less than or equal to 1/2.
Alternatively, PP can be defined using only deterministic Turing machines. A language L is in PP if and only if there exists a polynomial p and deterministic Turing machine M, such that
- M runs for polynomial time on all inputs
- For all x in L, the fraction of strings y of length p(|x|) which satisfy M(x,y) = 1 is strictly greater than 1/2
- For all x not in L, the fraction of strings y of length p(|x|) which satisfy M(x,y) = 1 is less than or equal to 1/2.
In both definitions, "less than or equal" can be changed to "less than" (see below), and the threshold 1/2 can be relaced by any fixed rational number in (0,1), without changing the class.
Read more about this topic: PP (complexity)
Famous quotes containing the word definition:
“Although there is no universal agreement as to a definition of life, its biological manifestations are generally considered to be organization, metabolism, growth, irritability, adaptation, and reproduction.”
—The Columbia Encyclopedia, Fifth Edition, the first sentence of the article on “life” (based on wording in the First Edition, 1935)
“Beauty, like all other qualities presented to human experience, is relative; and the definition of it becomes unmeaning and useless in proportion to its abstractness. To define beauty not in the most abstract, but in the most concrete terms possible, not to find a universal formula for it, but the formula which expresses most adequately this or that special manifestation of it, is the aim of the true student of aesthetics.”
—Walter Pater (1839–1894)
“Scientific method is the way to truth, but it affords, even in
principle, no unique definition of truth. Any so-called pragmatic
definition of truth is doomed to failure equally.”
—Willard Van Orman Quine (b. 1908)