# An Interactive Proof of God's Number?

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?
• 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." Nov 27 '10 at 2:29
• 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? Nov 27 '10 at 2:38
• @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. Nov 27 '10 at 20:18

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

• 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. Nov 27 '10 at 18:08
• @Peter: If by "practical" you mean the prover being BPP, then you are right. In fact, only NP languages have such proofs. Nov 27 '10 at 19:34
• I meant by "practical" something where the prover has roughly the same computational power as the proof that God's number = 20. Nov 27 '10 at 20:10
• 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. Nov 27 '10 at 20:27
• @sadeq: Maybe some problems in MA and AM might, but I'm not aware of anything outside these classes which have "practical" interactive proofs. Nov 27 '10 at 21:50

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.

• How much power does Merlin need to execute this protocol? At first glance it seems potentially much harder to find that specific word than it is to calculate the diameter by brute force. (I think this protocol is interesting from the point of view of someone asserting that a particular Markov chain has mixed --finding the word with the specific hash value seems much harder than running the chain for a long time...) Apr 19 '20 at 19:06
• @LorenzoNajt Thanks for taking the time to consider the above. Indeed! I think Merlin may need at least the power to solve an exponential number of $\mathsf{NP}$ certificates - the (inner) $\mathsf{NP}$ tests to find words that map to the given $g$, and the (outer) exponential to find the write word that hashes onto the given $y$. But, this may be common in $\mathsf{AM}$ protocols as discussed, e.g., here. (cont.) Apr 20 '20 at 16:36
• However, contrast this with the difficulty of finding the diameter of $G$. For example, for God's number tests I believe one must do an exponential number of $\mathsf{coNP}$ proofs. The (outer) exponential would hunt over all elements of $G$ for elements $g$ having (inner) $\mathsf{coNP}$ tests showing that $g$ cannot be written as a word smaller than $\Delta$. (con). Apr 20 '20 at 16:42
• As you indicate, clearly walking along the Cayley graph for a "long enough" time is quite easy to do, but nonetheless with the above, Arthur still just needs to randomly draw $g$, $h$, and $y$ to provide to Merlin, and could trivially verify whatever Merlin gives him. (finish) Apr 20 '20 at 16:46