Practice Final Answers - Post your answers here
Originally Posted By: jnewth
Problem 7: Show BPP is in Sigma-P2.
This proof is Sipser-Gacs presented pg 136 and the notes of November 28.
Proof Idea:
BPP is contained in the intersection of Sigma-P2 and Pi-P2 which can be simplified to Sigma-P2 because BPP=coBPP, i.e. BPP is closed under complementation.
If x is the language L in BPP, then there is a certificate r that causes M to accept x with some high probability. If x is not in the language, then there are a small number of certificates that will cause M to accept x erroneously. The rest of this proof uses the concept of "shifts" to show that thinking about the the sizes of these two sets of certificates (that cause M to accept x either correctly or incorrectly) can be phrased as a computation in Sigma-P2. Math ensues:
For a language in L in BPP:
x∈L⇒Pr[M(x,r)accepts]≥1-2^-n
x∉L⇒Pr[M(x,r)accepts]≤2^-n
For x of length n, Sx is the set of certificate "r" of length at most m for which M accepts .
If x∈L then size Sx = Pr(M(x,r) accepts correctly) * number of strings of length m
|Sx|>=(1-2^-n)*(2^m)
And by similar reasoning for x∉L
Sx = Pr(M(x, r) accepts erroneously) * number of strings of length m
|Sx| Shift: If we have a set of strings of length m and a shift string u of length m, we shift S by u by doing bitwise addition of every string in S with u, creating a new set of strings of the same size as the original set S. We generate a new set for each shift.
Claim 1: For every set S⊆{0,1}^m with |S|≤2^(m-n) and k vectors u1,...uk, the union of all strings for each shift Proof: The shift of the set has the same number of strings as the original set, so if we add all the shifted sets together, we would get at most k*|S| total strings. k*|S| strings is less than 2^m, the total possible number of strings of length m. This is because m=|r| (ie the length of a certificate) which can only be polynomial in n. The algebra is in the notes.
Claim 2: For every set S⊆{0,1}^m with |S|≥(1-2^-n)*(2^m), there exist u1,...,uk such that the union of all shifted sets = {0,1}^m
(IE A big enough set with k shifts CAN generate all 2^m strings of length m)
We want to show that there is at least SOME choice of shifts for which this is true. We do this by showing
Pr[there exists a string of length m that is not in S'] jnewth — Sat Dec 10, 2011 6:25 pm
<hr>
'''Originally Posted By: jnewth'''
<br>Problem 7: Show BPP is in Sigma-P2.<br><br><br>This proof is Sipser-Gacs presented pg 136 and the notes of November 28.<br><br>Proof Idea:<br>BPP is contained in the intersection of Sigma-P2 and Pi-P2 which can be simplified to Sigma-P2 because BPP=coBPP, i.e. BPP is closed under complementation.<br><br>If x is the language L in BPP, then there is a certificate r that causes M to accept x with some high probability. If x is not in the language, then there are a small number of certificates that will cause M to accept x erroneously. The rest of this proof uses the concept of "shifts" to show that thinking about the the sizes of these two sets of certificates (that cause M to accept x either correctly or incorrectly) can be phrased as a computation in Sigma-P2. Math ensues:<br><br>For a language in L in BPP:<br><br>x∈L⇒Pr[M(x,r)accepts]≥1-2^-n<br>x∉L⇒Pr[M(x,r)accepts]≤2^-n<br><br>For x of length n, Sx is the set of certificate "r" of length at most m for which M accepts .<br><br>If x∈L then size Sx = Pr(M(x,r) accepts correctly) * number of strings of length m <br>|Sx|>=(1-2^-n)*(2^m)<br><br>And by similar reasoning for x∉L<br><br>Sx = Pr(M(x, r) accepts erroneously) * number of strings of length m <br>|Sx| Shift: If we have a set of strings of length m and a shift string u of length m, we shift S by u by doing bitwise addition of every string in S with u, creating a new set of strings of the same size as the original set S. We generate a new set for each shift. <br><br>Claim 1: For every set S⊆{0,1}^m with |S|≤2^(m-n) and k vectors u1,...uk, the union of all strings for each shift Proof: The shift of the set has the same number of strings as the original set, so if we add all the shifted sets together, we would get at most k*|S| total strings. k*|S| strings is less than 2^m, the total possible number of strings of length m. This is because m=|r| (ie the length of a certificate) which can only be polynomial in n. The algebra is in the notes.<br><br>Claim 2: For every set S⊆{0,1}^m with |S|≥(1-2^-n)*(2^m), there exist u1,...,uk such that the union of all shifted sets = {0,1}^m<br><br>(IE A big enough set with k shifts CAN generate all 2^m strings of length m)<br><br>We want to show that there is at least SOME choice of shifts for which this is true. We do this by showing <br>Pr[there exists a string of length m that is not in S'] jnewth — Sat Dec 10, 2011 6:25 pm
<hr>