11
$\begingroup$

I've been learning about interactive proofs lately and I've been wondering if the whole thing was nothing more than a theoretical curiosity, or if it had any practical applications. I thought I'd start off with an example which occurred to me in the shower:

It's been making the news lately that "God's Number"=20. (God's number is the minimal number of steps needed to solve the Rubik's Cube). While this is pretty interesting, there seems to be a little twist ... This isn't a "normal" proof in the textbook, polynomial time verifiable sense. This proof has a distinctly "brute force" flavor to it - by this I mean, the dudes at Dr Morley's lab tried with billions and billions of combinations of cubes in Google's massive supercomputers to find this neat, tight lower bound.

Anyway, the question is: How can we be certain that Dr Morley Davidson and his team are honest? Well, right away can throw the argument from authority out of the window as it's not mathematically rigorous. The obvious alternative is to re-verify the proof, by checking the source code and running the whole thing again, which seems to be a terrible waste of computational resources, not to mention the fact that everybody who who wished to be convinced of this would need to do it on his own workstation - a very tedious and unpleasant proposition for the true skeptic. So this seems to be a kind of ontological deilema.

So what I believe is this is exactly a situation where we need an interactive proof. Google's Supercomputer could be the all powerful but deceptive Prover, and we the skeptical, if not anal members of the public are the Polynomially bounded Verifiers. If we could somehow query our "Oracle" a polynomial number of times, and be convinced of this lower bound, we could be convinced of the fact that he's right, beyond all reasonable doubt.

So it seems the Decision problem "God's Number is < 20" lies in $\Pi_2^p$ or can be restated as follows (informally)

For all starting combinations $\alpha$ in the Rubik's Cube, there exists a solution which takes <=20 steps, $\beta$ which solves it.

(not sure if that's correct, but $\alpha$ and $\beta$ are both small in size, given a starting configuration and a solution it's easy to verify that it does indeed solve the cube)

and the Decision problem "God's number is 20" can be restated as

God's number is <20 and there exists a solution for some starting combination of the Rubik's cube which takes 20 steps.

So there's probably a IP[n] proof for this. (once again, check my workings)

My question is twofold

  1. Is there a actual way to do this?
  2. What other examples of "pratical" uses of interactive proofs are there?
$\endgroup$
  • $\begingroup$ I think you mean "God's number" is the maximum number of moves needed to solve the Rubix Cube. Similarly you mention some number of times "this neat, tight lower bound" while you mean "upper bound." $\endgroup$ – Ross Snider Nov 27 '10 at 2:29
  • 1
    $\begingroup$ Anyway, a partial answer to your question. There is a possibly related question cstheory.stackexchange.com/questions/2461/…. To my understanding the answer to your first question is yes - just follow the protocol. However, it's also my understanding that actually engaging in an interactive proof setting has not "caught on." Does anyone know if the constants involved are very high? $\endgroup$ – Ross Snider Nov 27 '10 at 2:38
  • $\begingroup$ @Ross Snider: sorry, my mistake :( Corrected. As for your second point, yes. However I don't think the problem is with large constants in the Verifier, but too much burden on the "Prover". IP[n] would require the Verifier to do be a lot more powerful than $\Pi_2$ (where google is at), but in fact the procedure would require it to be more powerful than $PSPACE$, making it "impractical", I suppose, the link you posted was very helpful, thank you. $\endgroup$ – gabgoh Nov 27 '10 at 20:18
10
$\begingroup$

... it seems the Decision problem "God's Number is < 20" lies in $\Pi_2^p$.

That is enough for it to have an interactive proof. In fact, Lund et al. proved that every language in polynomial hierarchy (PH) has an interactive proof by using Toda's theorem ($\rm{PH} \subseteq P^{\#P}$). They reduced $L\in \rm{PH}$ to #P-complete language PERMANENT, and provided an algebraic method which can be used to prove PERMANENT interactively. (This is highly inaccurate; please refer to the paper for more info.)

Using their techniques, Shamir proved that IP=PSPACE.

It was previously proved that all IP has zero-knowledge proofs, so:

All languages in PSPACE have zero-knowledge interactive proofs.

$\endgroup$
  • $\begingroup$ But proving something in $\Pi_2$ with an interactive proof generally means solving a P$^{\#\mathrm{P}}$ problem (cstheory.stackexchange.com/questions/2461/…), so if you're looking for practical interactive proofs, this won't do it. $\endgroup$ – Peter Shor Nov 27 '10 at 18:08
  • $\begingroup$ @Peter: If by "practical" you mean the prover being BPP, then you are right. In fact, only NP languages have such proofs. $\endgroup$ – M.S. Dousti Nov 27 '10 at 19:34
  • $\begingroup$ I meant by "practical" something where the prover has roughly the same computational power as the proof that God's number = 20. $\endgroup$ – Peter Shor Nov 27 '10 at 20:10
  • 1
    $\begingroup$ Thank you for the response, but as Shor comments, by "Practical" I mean something which might actually be implementable, not possible in principle. To see the gist of it, here's an example a "Practical" proof system which doesn't prove anything. [I give the prover a random starting configuration $\alpha$, and the prover returns a sequence of moves in less than 20 steps which solves it. I try this a bunch of times.] Of course, this won't work, but this is sort of the thing I'm looking for. $\endgroup$ – gabgoh Nov 27 '10 at 20:27
  • 2
    $\begingroup$ @sadeq: Maybe some problems in MA and AM might, but I'm not aware of anything outside these classes which have "practical" interactive proofs. $\endgroup$ – Peter Shor Nov 27 '10 at 21:50
1
$\begingroup$

Determining that $20$ is the diameter (God's number) of the Rubik's Cube Group $G$ under the half-turn metric with Singmaster generating set $s=\langle U, U', U^2, D, D', D^2,\cdots\rangle$ was a wonderful result. I'm curious about follow-up questions, such as determining how many half-turn twists $m$ it would take to get the cube fully "mixed" to $\epsilon$-close to the uniform stationary distribution $\pi$.

I believe that such mixing exhibits a cut-off wherein for $n\lt m$, some configurations are much more likely than others, whereas for $n\ge m$ the cube is almost fully scrambled to the uniform distribution $\pi$, and no large subset $A\subset G$ of configurations is disfavored. There might be a promise at the heart of any mixing that exhibits such a cut-off. This promise can be leveraged to create an Arthur-Merlin $\mathsf{AM}$ protocol.

For example, noting that $\vert s \vert=18$ and calling $m$ the to-be-verified mixing time, I think we can promise:

  • If $n\ge m$ then for all but a very small number, $\epsilon$, of elements $g\in G$ there are very close to $\frac{18^n}{\vert G \vert}$ ways of writing $g$ as words in $s$ of length $\le n$, and

  • If $n \lt m$, then there are a much larger number, $k=\vert A\vert$, of elements $g\in G$ where $g$ can only be written in at most $\frac{18^n}{2 \vert G \vert}$ ways as words of length $\le n$.

Here I think of $\epsilon$ as, say, $\frac{1}{10^9}\vert G\vert$, and $k$ as, say $\frac{1}{10}\vert G\vert$.

Standard universal hashing tricks create a single round Arthur-Merlin proof that the mixing time is at least $n$.

  1. Arthur chooses a random element $g\in G$, a random hash $h$ mapping words of $G$ onto a set of size $\frac{18^n}{\vert G \vert}$, and a random image $y$ of $h$
  2. Merlin tells Arthur a word $W$ of length up to $n$ that, when applied to the starting position of the cube, equals $g$
  3. The word $W$ must also satisfy $h(W)=y$ - indicating that there are likely a lot of words of length $\le n$ that equal $g$
  4. Arthur and Merlin repeat to amplify as needed

Because, for groups I think, the mixing time is at least the diameter (God's number), this also provides an Arthur-Merlin proof to bound the God's number of a large group.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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