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:
“The definition of good prose is proper words in their proper places; of good verse, the most proper words in their proper places. The propriety is in either case relative. The words in prose ought to express the intended meaning, and no more; if they attract attention to themselves, it is, in general, a fault.”
—Samuel Taylor Coleridge (1772–1834)
“... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lens—if we are unaware that women even have a history—we live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.”
—Adrienne Rich (b. 1929)
“It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.”
—François, Duc De La Rochefoucauld (1613–1680)