Statement of The Lemma
The generalized version of the lemma is stated as follows. Let A be a probabilistic algorithm, with inputs (x, h1, ..., hq; r) that outputs a pair (J, y), where r refers to the random tape of A (that is, the random choices A will make). Suppose further that IG is a probability distribution from which x is drawn, and that H is a set of size h from which each of the hi values are drawn according to the uniform distribution. Let acc be the probability that on inputs distributed as described, the J output by A is greater than or equal to 1.
We can then define a "forking algorithm" FA that proceeds as follows, on input x:
- Pick a random tape r for A.
- Pick h1, ..., hq uniformly from H.
- Run A on input (x, h1, ..., hq; r) to produce (J, y).
- If J = 0, then return (0, 0, 0).
- Pick h'J, ..., h'q uniformly from H.
- Run A on input (x, h1, ..., hJ−1, h'J, ..., h'q; r) to produce (J', y').
- If J' = J and hJ ≠ h'J then return (1, y, y'), otherwise, return (0, 0, 0).
Let frk be the probability that FA outputs a triple starting with 1, given an input x chosen randomly from IG. Then
Read more about this topic: Forking Lemma
Famous quotes containing the words statement of and/or statement:
“Truth is used to vitalize a statement rather than devitalize it. Truth implies more than a simple statement of fact. I dont have any whisky, may be a fact but it is not a truth.”
—William Burroughs (b. 1914)
“The new statement is always hated by the old, and, to those dwelling in the old, comes like an abyss of skepticism.”
—Ralph Waldo Emerson (18031882)