I was reading a paper by Lance Fortnow and Michael Sipser. "Are there interactive protocols for co-NP languages?" Information Processing Letters 28 v5 (1988), pp. 249-251. An online version of the paper can be found at http://lance.fortnow.com/papers/files/conpipl.pdf.

My question concerns the second part of the proof (the last paragraph), in the case we have a prover which makes $V_i$ accept with probability 2/3: I am not sure why there must exist an oracle query $x$ of length $N_i$ that appears in at most $p_i/2^{N_i}$ computation paths. Shouldn't there be $2^{M_i}$ computation paths where $M_i = poly(N_i)$ is the number of random bits? So then some $x$ must appear in $p_i*2^{M_i}/2^N_i$ paths, which is not clearly small.

For reference, I am reproducing the proof below:

We want to prove that there exists an oracle A and a language $L \in \mathrm{coNP}^A$ such that $L \not\in \mathrm{IP}^A$.

For any oracle $A$, let $L(A) = \{ 1^n : \text{$A$ contains all strings of length $n$}\}$. It is clear that $L(A) \in \mathrm{coNP}^A$ for all oracles $A$. We will create $A$ in stages. At each stage we look at some finite set of strings. For each string in this set, we decide whether to include or exclude this string from A. In stage $i$, we choose the set of strings so that $L(A)$ does not have an interactive protocol with verifier $V_i$. Thus, after the construction, $L(A)$ cannot have an interactive protocol and we have proved our statement.

Stage $i$: Pick $N_i$ large enough so $2^{N_i} > 3(N_i)^i$ and no oracle queries of length $N_i$ have been asked in any previous step. Let $p_i = (N_i)^i$. We will determine some strings of $A$ such that either $1^{N_i} \in L(A)$ and no prover can convince $V_i$ to accept $1^{N_i}$, or $1^{N_i} \not\in L(A)$ but there is a prover that will cause $V_i$ to accept. Every time $V_i$ makes an oracle query which hasn't been previously answered, we answer yes.

If there aren't any provers $P$ such that $P$ and $V_i$ accept on input $1^{N_i}$ with probability at least 2/3 then we put in the oracle $A$ all strings of length $N_i$ and every other previously unset string that $V_i$ asks about for any prover. This completes step $i$. Note that $V_i$ can only make queries of length less than $p_i$ so will will always be able to find $N_{i+1}$ in step $i+1$.

Otherwise we have some prover $P$ such that $P$ and $V_i$ will accept $1^{N_i}$ with probability at least 2/3. On any computation path (which is determined by $V_i$'s coin tosses), $V_i$ can ask at most $p_i$ oracle queries of length $N_i$. Since the same number of coin tosses are used during each round, the probability of each computation path is identical. There is some oracle query $x$ of length $N_i$ that appears in at most $p_i/2^{N_i}$ of the computation paths of $V_i$. By the way we chose $N_i$, this means that the oracle query $x$ appears in fewer than one-third of the computation paths of $V_i$. We put all the strings of length $N_i$ except for $x$ in the oracle A, and also place in the oracle every string queried by $V_i$ on every possible communication with $P$. $P$ will convince $V_i$ to accept with probability greater than one-third since more than a third of the computation paths are the same as before. So we are done with step $i$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.