Consider some $L \subseteq \{0,1\}^*$. Suppose Alice gives Bob a machine or oracle $M$ that purportedly decides $L$. If Bob has only polynomial time in their disposal, then they cannot directly test $M$ unless they already know a polynomial time algorithm for $L$. However, if $L \in \textsf{PSPACE}$ then Alice might be able to convince Bob via an interactive proof protocol. That is, Bob can generate random instances of the problem of size $n$, run $M$ and have Alice demonstrate the correctness of the answer. If they repeat the procedure sufficiently many times then Bob knows that, with high probability, $M$ gives the correct answer on most instances of size $n$, so it is at least "average-case" valid.

Now, if Alice is also limited to polynomial-time, then in general they won't be able to supply an interactive proof. Indeed, if it is possible for both the verifier and the prover to be polynomial-time, it follows that $L \in \textsf{BPP}$.

The motivation for the question is: what happens if $L$ is in $\textsf{BPP}$, but Bob doesn't know the algorithm for solving it? In this case, it is possible that Bob knows an interactive proof protocol for some class that is known to contain $L$ and Alice is able to fill in the role of prover. For example, if Alice tells Bob a polynomial-time algorithm for solving graph isomorphism then Bob can easily convince themselves of its validity (for given input size) because there is an interactive proof protocol where the prover can run in polynomial-time given oracle access to the problem. However, this example requires using a protocol specifically tailored to graph isomorphism, whereas I would like a protocol that can work for any problem in a large class (optimally all of $\textsf{PSPACE}$).

I am interested in all results that are relevant to the above discussion, but to make the question concrete, I will suggest a specific hypothesis.


Given a polynomial-time computable mapping $f: \{0,1\}^* \rightarrow \{0,1\}^*$, we can consider the language $f^{-1}(\textsf{TQBF}) \in \textsf{PSPACE}$.

We say that such an $f$ is easy when there is a polynomial-time algorithm that implements an optimal strategy for the corresponding game. That is, given $x \in \{0,1\}^*$, $k \in \mathbb{N}$ and any assignment of the variables corresponding to the $k$ outermost quantifiers in the formula represented by $f(x)$, our algorithm can decide whether the resulting formula (with quantifiers over unassigned variables) is true. In particular, in this case $f^{-1}(\textsf{TQBF}) \in \textsf{P}$.

Is there an interactive proof protocol for $\textsf{TQBF}$ s.t. for any easy $f$, there is some polynomial-time algorithm that, given input $x$, plays the role of the prover in the protocol for $f(x)$?

To understand the motivation for the easiness condition, note that if $f$ is s.t. the formulas it produces only have existential quantifiers (which implies $f^{-1}(\textsf{TQBF}) \in \textsf{NP}$) then the condition requires that not only $f^{-1}(\textsf{TQBF}) \in \textsf{P}$ but that the $\textsf{NP}$-witnesses can be produced in polynomial time (in fact it is even stronger: we should be able to complete any prefix to an $\textsf{NP}$-witness whenever possible).

  • $\begingroup$ How can Bob "easily convince themselves of its validity (for given input size)" if "Alice tells Bob a polynomial-time algorithm for solving graph isomorphism"? ​ (On the other hand, Bob can easily convince himself of its validity for a given input.) ​ ​ ​ ​ $\endgroup$ – user6973 Nov 17 '16 at 1:25
  • $\begingroup$ @RickyDemer Validity in some "average case" sense, i.e. they can test the algorithm on polynomially many random inputs, thus verifying that, with high probability, the algorithm only errs on a fraction $O(n^{-d})$ of the inputs. $\endgroup$ – Vanessa Nov 17 '16 at 6:20
  • 1
    $\begingroup$ Well then, Check generalizes that. ​ ​ $\endgroup$ – user6973 Nov 17 '16 at 6:28
  • $\begingroup$ @RickyDemer Yeah, this is definitely related, but I am interested in something slightly different. I want a (large as possible) class of languages $X$ s.t. (i) there is some way of formally describing a decision problem in $X$ e.g. $X$ contains a complete problem so we can formally describe any problem in $X$ by specifying the reduction (ii) There is a "universal" IPP for all problems in $X$ e.g. an IPP for the complete problem (iii) If some formally described problem happens to be easy in some sense (and in particular is in $BPP$) then a polynomial-time prover can implement the protocol. $\endgroup$ – Vanessa Nov 17 '16 at 6:38
  • $\begingroup$ "to graph isomorphism" ​ -> ​ "to non-isomorphism problems" ​ ​ ​ ​ $\endgroup$ – user6973 Nov 17 '16 at 6:58

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.