patternMinor
Prove that PP is closed under complement
Viewed 0 times
closedproveunderthatcomplement
Problem
I found this proof in Wikipedia, but one of the most important steps in it doesn't make any sense to me. I'll explain:
By the definition of PP there is a polynomial-time probabilistic
algorithm A with the property that ${x\in L\Rightarrow \mathrm {Pr}
[A(x) = 1]>\frac{1}{2}} $ and ${x\not \in L\Rightarrow \mathrm {Pr} [A(x) = 1]\leq \frac{1}{2}}$.
Let $f(|x|)$ be the
polynomial upper bound on the running time of A on input x. Thus A
makes at most $f(|x|)$ random coin flips during its execution. In
particular, $ x\in L\Rightarrow {\mathrm {Pr}}[A(x) = 1]\geq \frac{1}{2}+\frac{1}{2^{{f(|x|)}}}$.
I understand that:
[A(x) = 1]>\frac{1}{2}} $. It means that if indeed $x \in L$, more than half of the possible coin flip combinations would cause the algorithm to accept.
But why is it so obvious that $ x\in L\Rightarrow {\mathrm {Pr}}[A(x) = 1]\geq \frac{1}{2}+\frac{1}{2^{{f(|x|)}}}$?
That one specific combination of coin flips could easily be one of the half that was already counted in the definition of PP, and in that case, it would not make any sense add together "half of the possible coin flip combinations and one specific combination". What am I missing here?
By the definition of PP there is a polynomial-time probabilistic
algorithm A with the property that ${x\in L\Rightarrow \mathrm {Pr}
[A(x) = 1]>\frac{1}{2}} $ and ${x\not \in L\Rightarrow \mathrm {Pr} [A(x) = 1]\leq \frac{1}{2}}$.
Let $f(|x|)$ be the
polynomial upper bound on the running time of A on input x. Thus A
makes at most $f(|x|)$ random coin flips during its execution. In
particular, $ x\in L\Rightarrow {\mathrm {Pr}}[A(x) = 1]\geq \frac{1}{2}+\frac{1}{2^{{f(|x|)}}}$.
I understand that:
- By definition of PP, ${x\in L\Rightarrow \mathrm {Pr}
[A(x) = 1]>\frac{1}{2}} $. It means that if indeed $x \in L$, more than half of the possible coin flip combinations would cause the algorithm to accept.
- The algorithm's running time is bound by $f(|x|)$, then the probability of getting some specific combination of coin tosses (that accepts or rejects, we do not know) is bound by $(\frac{1}{2})^{f(|x|)} = \frac{1}{2^{{f(|x|)}}}$.
But why is it so obvious that $ x\in L\Rightarrow {\mathrm {Pr}}[A(x) = 1]\geq \frac{1}{2}+\frac{1}{2^{{f(|x|)}}}$?
That one specific combination of coin flips could easily be one of the half that was already counted in the definition of PP, and in that case, it would not make any sense add together "half of the possible coin flip combinations and one specific combination". What am I missing here?
Solution
$\frac{1}{2^{f(|x|)}}$ is the granularity of the probabilities. The probability distribution is over the possible outcomes of the coin flips. If you flip two coins for example, the probability that you accept can't be exactly 0.501. It's either 0 (you never accept), 1/4 (one coin flip combination leads to acceptance), 1/2 (two combinations make you accept), 3/4 or 1.
So if you require the probability to be greater than 1/2 you know that it's at least $1/2 + \frac{1}{2^{f(|x|)}}$.
So if you require the probability to be greater than 1/2 you know that it's at least $1/2 + \frac{1}{2^{f(|x|)}}$.
Context
StackExchange Computer Science Q#62642, answer score: 3
Revisions (0)
No revisions yet.