Suppose for each positive integer $N$, we have a graph $G_N$ with $N$ vertices labelled $1$ to $N$ (so $\log N$ bits are required to specify a vertex). Suppose we have a PSPACE algorithm to determine whether two given vertices in $G_N$ are adjacent (ie the space used is $P(\log N)$ for some polynomial $P$). Consider the following decision problem:
Given integers $N,M$ and vertices $a,z$ in $G_N$, is there a path of length $\leq M$ from $a$ to $z$ in $G_N$?
(the size of the input is $3\log N+\log M$ bits). We can answer this problem using the following recursive algorithm:
def exists_path(N,M,a,z):
if M == 0: return a == z
if M == 1: return are_adjacent(N,a,z)
for b = 1 to N:
if exists_path(N,M/2,a,b) and exists_path(N,(M+1)/2,b,z): return True
return False
The recursion depth is $\log M$, so the space used is $(3\log N+\log M)\log M+P(\log N)$. In particular the problem is in PSPACE. Since IP=PSPACE, there must be an IP algorithm for this problem. In theory I can follow the proofs on wikipedia to encode the problem as a TQBF problem... but I doubt the result will be pretty.
Is there an explicit IP algorithm for this problem?
I'm happy to assume the adjacency problem is actually in P if it makes things simpler.
Note that we can't just treat the adjacency algorithm as a black box. Indeed fix $k\in(0,1)$ and consider two possible adjacency functions:
def are_adjacent1(N,a,z):
return z == a + 1
def are_adjacent2(N,a,z):
return z == a + 1 and a != ceil(k*N)
These represent graphs $G_N,G_N'$ where $G_N$ is a path graph and $G_N'$ is the same minus a single edge. Now hand are_adjacent1 to an honest prover and are_adjacent2 to an honest verifier. Since the verifier can only make $O(\log N)$ calls to the adjacency function, with high probability it will never check the single missing edge, and be convinced that vertices $1$, $N$ are connected in $G_N'$, which is false.
