5
$\begingroup$

There is an extremely standard proof that IP⊆PSPACE, used for instance here, here, or here, by the argument that the full protocol is max-avg game tree that can be evaluated in polynomial space. It's really clean and, dare I say, obvious as a first example of a simulation argument. Great! But that works as long as all coins are public. This one makes this explicit at least, defining IP in terms of message histories.

But this isn't how people talk about IP in practice! The classic graph non-isomorphism protocol, as it's presented to students, in private-coin; the same goes for the standard PSPACE⊆IP proof. In fact, IP[k] is often explicitly used to mean private coins, while AM[k] is used to mean public coins. I'm aware that private-coin and public-coin are equivalent, this was the substance of Goldwasser+Sipser "Private Coins vs. Public Coins in Interactive Proof Systems", but it is nontrivial. My question is if there's a simple explanation that IP⊆PSPACE that doesn't require going through this.

If you take the 'standard' proof that IP⊆PSPACE and try to apply it with private coins, it doesn't work; now the prover's response needs to depend only on the message and not the coins, so it no longer forms a tree.

If I was teaching this, I would prefer not to define IP one way, then give a proof for a materially different definition. Is there a good way to see that IP⊆PSPACE even with private coins?

$\endgroup$
3
  • $\begingroup$ I am not sure I understand your question. Can you elaborate? Any transcript of messages has at most polynomial size. Given a partial transcript of $i$ rounds $(a_1, b_1, \ldots, a_i, b_i)$, we can compute in polyspace the next "best" message to send by also iterating over all possible random choices. So even if the random coins of the verifier are private, we can iterate over all possible choices and consider ones that are consistent with the partial transcript of the interaction so far. $\endgroup$ Commented Jan 22 at 23:09
  • $\begingroup$ That's a perfect answer, thanks. That's a good explanation and not one I had seen. My "question" was that none of those three first links suggested something like that - each node of the game tree is just evaluated in terms of its children, and not also averaging over the unseen coins, and the extension wasn't clear to me. If you write your comments as an answer I'll happily accept it. $\endgroup$ Commented Jan 23 at 15:37
  • $\begingroup$ I will write it as a detailed answer, writing the recursion traversal of the tree explicitly, if that helps. $\endgroup$ Commented Jan 23 at 17:31

1 Answer 1

3
$\begingroup$

Following the comments, below is a sketch of the proof that shows explicitly that there is no need for the coins to be public, as we can iterate over all random choices in polynomial space.

Sketch of the proof that $\text{IP} \subseteq \text{PSAPCE}$: consider a language $L \in \text{IP}$, and let $(P, V)$ be an interaction protocol for $L$. It is sufficient, for all $x\in L$, to compute the quantity $cp_x = \max\limits_{\widetilde{P}} \Pr\limits_{r} \ [\langle \widetilde{P}, V(x, r) \rangle]$ in polynomial space (intuitively, $cp_x$ is the maximal convincing probability for $V$ on input $x$). Indeed, if $x\in L$, then $cp_x \geq \frac{2}{3}$ as for example this quantity is obtained when we consider completeness w.r.t the prover $P$, and if $x\notin L$, then by soundness $cp_x$ is at most $\frac{1}{3}$. Hence, a PSPACE algorithm first computes $cp_x$, on input $x$, and accepts only when $cp_x \geq \frac{2}{3}$.

Note that it is okay to write "max" although there are infinitely many potential provers. The point is that we need not iterate over all provers, but rather over all transcripts of at most polynomial size and there are finitely many. Having this intuition in mind, we can compute the best prover strategy, denoted $P_b$, a one that maximizes the convincing probability $cp_x$. Once we have $P_b$, we can obtain $cp_x$, to be detailed below.

We can treat $P_b$ as a function from partial transcripts, describing $i$ rounds of interaction so far, to the next message $a_{i+1}$ to be sent by the prover, such that $a_{i+1}$ maximizes the convincing probability conditioned on the past partial transcript that we had so far. Thus, $P_b(x, a_1, b_1, a_2, b_2, \ldots, a_i, b_i) = a_{i+1}$, where $a_k$ and $b_k$ are the $k$'th messages of the prover and the verifier, respectively.

It is not hard to see that, for input $x$, computing the best prover strategy $P_b$ in polynomial space is sufficient. Indeed, if we have $P_b$, then $cp_x$ is simply obtained by $$ cp_x = \frac{\sum\limits_{r\in R} 1_{[\langle P_b, V(x, r) \rangle = 1]}} {|R|}$$

where $R = \{ 0, 1\}^{p(|x|)}$ describes the randomness of the verifier $V$ on input $x$, and $p$ is a polynomial bounding the runtime of $V$. Indeed, for every random string $r \in R$, it is easy to simulate in polynomial space the interaction between $P_b$ and $V$ on input $x$. Hence, if $P_b$ can be computed in polynomial space, then so is $cp_x$.

So to conclude the proof it suffices to compute $P_{b}$ in polynomial space, for every input $x$. We can compute $P_{b}$ by induction on the total number of rounds $t$ (note that $t$ is also bounded by a polynomial in $|x|$).

  • The base case is the case where we have survived $i = t-1$ rounds of the interaction. Let $(a_1, b_1, a_2, b_2, \ldots, a_i, b_i)$ denote the history of the interaction so far. Then, $$ P_b(x, a_1, b_1, a_2, b_2, \ldots, a_i, b_i) = \arg\max\limits_{a_t} \mathop{\mathbb{E}}_{r \in R[x, i]} [V(x, r, a_1, a_2, \ldots, a_{t-1}, a_t)]$$ where $R[x, i]$ is the set of random strings that are consistent with $x$ and the partial transcript $(a_1, b_1, a_2, b_2, \ldots, a_i, b_i)$. Note that it is easy to iterate over all random strings $r$ and check which ones are in $R[x, i]$ in polynomial space. All you need to do to simulate the interaction with the current random string $r$ and input $x$, and check if the answers induced by it are consistent with the partial transcript. So the outer loop remembers the best $a_t$, and the inner loop iterates over all consistent randomness $r$ (even if it is private, we can do that as we can afford it in polynomial space). Both loops can be computed in polynomial space each -- recall the the length of the message $a_t$ is at most polynomial, so we can iterate over all potential $a_t$'s in polynomial space.

  • The induction step is the case where we have survived $i < t-1$ rounds of the interaction. Let $(a_1, b_1, a_2, b_2, \ldots, a_i, b_i)$ denote the history of the interaction so far. Then, $$ P_b(x, a_1, b_1, a_2, b_2, \ldots, a_i, b_i) = \arg\max\limits_{a_{i+1}} \mathop{\mathbb{E}}_{r \in R[x, i]} [V(x, r, a_1, a_2, \ldots, a_{i}, a_{i+1}, a^*_{i+2}, \ldots, a^*_t)]$$

where $a^*_j$ is the best prover message obtained by simulating an interaction that is consistent with $x, r, a_{i+1}$ and $(a_1, b_1, \ldots, a_i, b_i)$. So once $a_{i+1}$ and $r$ are fixed and we are in the inner loop, we can compute $b_{i+1} = V(x, r, a_1, a_2, \ldots, a_{i+1})$, $a^*_{i+2} = P_b(x, r, a_1, b_1, \ldots,a_{i+1}, b_{i+1} )$ and proceed similarly to compute $b_{i+2}$ and $a^*_{i+3}$, etc. The point is that inside the inner loop, we can compute $a^*_j$ in polynomial space as we are applying the induction hypothesis and computing $P_b$ on transcripts with $ > i$ rounds. So we kinda open an inner third loop to do that, but it takes at most polynomial space in total as the induction assumption takes care of that.

Note: We're actually traversing a tree that has polynomial depth, and exponential fan-out. The base case corresponds to the leaves of the tree. So we have the max-nodes and average-nodes, and to compute the root's value, we kinda apply a standard tree traversal algorithm, which takes at most polynomial space.

Credit to: I recall the idea from a lecture of Alessandro Chiesa that I saw online two years ago, but unfortunately I do not recall where or whether it is still up there.

$\endgroup$
2
  • $\begingroup$ Much appreciated, thanks! $\endgroup$ Commented Jan 23 at 21:53
  • $\begingroup$ You're welcome! $\endgroup$ Commented Jan 23 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.