2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Try implementing "binary search". The prover is claiming that there is a path of length $M$ from $a$ to $z$, with middle vertex $b$. The verifier chooses to verify either the leg from $a$ to $b$ or the leg from $b$ to $z$. Continue in this way until you reach a claimed edge, which can be verified directly. $\endgroup$ – Yuval Filmus May 9 '18 at 6:33
  • $\begingroup$ @YuvalFilmus I was thinking along these lines but I don't think it works. A cheating prover picks a path of length $M/2$ from $a$ or $z$ (chosen randomly) to $b$, and claims $b$ is the midpoint. The verifier will be tricked if they make an unfortunate leg choice just once (which has high probability). Normally in these proofs the verifier is tricked only if every choice is unfortunate. $\endgroup$ – stewbasic May 9 '18 at 6:40
  • $\begingroup$ @stewbasic, can you repeat this proof strategy polynomially times to get the probability of false acceptance down to something exponentially small? $\endgroup$ – D.W. May 9 '18 at 22:06
  • $\begingroup$ @D.W. I don't think so. Suppose $N=M$ and the cheating prover is lying about only one edge. Then the chance of being fooled is $1-1/M$. Repeat $k$ times; the chance of being fooled is $(1-1/M)^k\geq1-k/M\approx 1$ if $k$ is bounded by a polynomial in $\log M$. $\endgroup$ – stewbasic May 9 '18 at 22:30

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.