<h1>Motivation</h1>

<p>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.</p>

<p>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}$. </p>

<p>The motivation for the question is: <em>what happens if $L$</em> is <em>in $\textsf{BPP}$, but Bob doesn't know the algorithm for solving it?</em> 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}$).</p>

<p>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.</p>

<h1>Question</h1>

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

<p>We say that such an $f$ is <em>easy</em> 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}$.</p>

<blockquote>
  <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)$?</p>
</blockquote>

<p>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).</p>

CC BY-SA 3.0
2016-11-17T06:20:34.120Z
@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.
Vanessa
CC BY-SA 3.0
2016-11-17T06:38:19.697Z
@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.
Vanessa
CC BY-SA 3.0
2016-11-17T07:06:29.090Z
@RickyDemer Well, it uses something about graphs, namely that there is a "scrambling" procedure s.t. given two isomorphic graphs the scrambled graphs are distributed in the same way. I'm not sure whether there is an accepted name for this?
Vanessa
<cc.complexity-theory><interactive-proofs><pspace>
Easy interactive proofs for easy problems?
Vanessa
# Easy interactive proofs for easy problems?

(Asked by: username_0 on 2016-11-16)

# Motivation

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.

# Question

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).

**Tags:** cc.complexity-theory, interactive-proofs, pspace

> **Comments:**
> **username_0**: @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.  
> **username_0**: @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.  
> **username_0**: @RickyDemer Well, it uses something about graphs, namely that there is a "scrambling" procedure s.t. given two isomorphic graphs the scrambled graphs are distributed in the same way. I'm not sure whether there is an accepted name for this?  

---

## 0 answers

