<blockquote>
  <p>... it seems the Decision problem "God's Number is &lt; 20" lies in $\Pi_2^p$.</p>
</blockquote>

<p>That is enough for it to have an interactive proof. In fact, <a href="http://portal.acm.org/citation.cfm?id=146585.146605" rel="noreferrer">Lund <em>et al.</em></a> 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.)</p>

<p>Using their techniques, Shamir proved that <a href="http://portal.acm.org/citation.cfm?id=146609" rel="noreferrer">IP=PSPACE</a>.</p>

<p>It was previously proved that <a href="http://www.springerlink.com/content/f2xw2nbwb2kqkewp/" rel="noreferrer">all IP has zero-knowledge proofs</a>, so:</p>

<p>All languages in PSPACE have zero-knowledge interactive proofs.</p>

CC BY-SA 2.5
2010-11-27T18:08:08.387Z
But proving something in $\Pi_2$ with an interactive proof generally means solving a P$^{\#\mathrm{P}}$ problem (http://cstheory.stackexchange.com/questions/2461/interactive-proofs-for-levels-of-the-polynomial-hierarchy), so if you're looking for practical interactive proofs, this won't do it.
Peter Shor 
CC BY-SA 2.5
2010-11-27T19:34:08.793Z
@Peter: If by "practical" you mean the prover being BPP, then you are right. In fact, only NP languages have such proofs.
Sadeq Dousti
CC BY-SA 2.5
2010-11-27T20:10:41.383Z
I meant by "practical" something where the prover has roughly the same computational power as the proof that God's number = 20.
Peter Shor 
CC BY-SA 2.5
2010-11-27T20:27:20.460Z
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.
gabgoh
CC BY-SA 2.5
2010-11-27T20:46:30.183Z
@gabgoh: If deciding the problem "God's Number is < 20" lies in $\Pi_2$ you are out of luck (unless PH collapses to NP). As I said, only NP has "practical" interactive proofs. After all, if the prover cannot decide something (even after getting a short witness), he will be unable to prove it to anyone else.
Sadeq Dousti
CC BY-SA 2.5
2010-11-27T21:50:25.653Z
@sadeq: Maybe some problems in MA and AM might, but I'm not aware of anything outside these classes which have "practical" interactive proofs.
Peter Shor 
CC BY-SA 2.5
2010-11-28T13:25:39.003Z
@Peter: I don't think a polynomial-time prover can decide hard languages in either MA or AM, even if he is given any short witness. (This is true unless MA = NP or AM = NP.)
Sadeq Dousti
CC BY-SA 2.5
2010-11-28T15:07:37.960Z
@Sadeq: MA is practical. There's a classical witness and a BPP program which checks that witness. All you need is a trusted random number generator. Second, this question was about two computers in the real world with vastly different amounts of power, so just saying that it's not in P may not be enough. I wouldn't be surprised if somebody came up with instances of graph isomorphism where there's a superpolynomial but not too impractical algorithm for distinguishing them, in which case you might have practical interactive proofs for some problems in AM.  Beyond that, I believe, is hopeless.
Peter Shor 
CC BY-SA 2.5
2010-11-28T16:51:56.703Z
@Peter: You are right about MA. I didn't know why I made such stupid mistake :) As you said, "[there] might [be] practical interactive proofs for some problems in AM." Yes, and there are. In fact, since $NP \subseteq AM$, there are already such proofs. Yet unless $AM = MA$, I believe some problems in AM won't have "practical" interactive proofs.
Sadeq Dousti
CC BY-SA 2.5
2010-11-27T03:57:04.253Z
2010-11-28T16:28:34.343Z
2010-11-28T16:28:34.343Z
Sadeq Dousti
<p>Determining that <span class="math-container">$20$</span> is the diameter (God's number) of the Rubik's Cube Group <span class="math-container">$G$</span> under the half-turn metric with Singmaster generating set <span class="math-container">$s=\langle U, U', U^2, D, D', D^2,\cdots\rangle$</span> was a wonderful result.  I'm curious about follow-up questions, such as determining how many half-turn twists <span class="math-container">$m$</span> it would take to get the cube fully "mixed" to <span class="math-container">$\epsilon$</span>-close to the uniform stationary distribution <span class="math-container">$\pi$</span>.  </p>

<p>I believe that such mixing exhibits a <em>cut-off</em> wherein for <span class="math-container">$n\lt m$</span>, some configurations are much more likely than others, whereas for <span class="math-container">$n\ge m$</span> the cube is almost fully scrambled to the uniform distribution <span class="math-container">$\pi$</span>, and no large subset <span class="math-container">$A\subset G$</span> 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 <em>Arthur-Merlin</em> <span class="math-container">$\mathsf{AM}$</span> protocol.</p>

<p>For example, noting that <span class="math-container">$\vert s \vert=18$</span> and calling <span class="math-container">$m$</span> the to-be-verified mixing time, I think we can promise:</p>

<ul>
<li><p>If <span class="math-container">$n\ge m$</span> then for all but a very small number, <span class="math-container">$\epsilon$</span>, of elements <span class="math-container">$g\in G$</span> there are very close to <span class="math-container">$\frac{18^n}{\vert G \vert}$</span> ways of writing <span class="math-container">$g$</span> as words in <span class="math-container">$s$</span> of length <span class="math-container">$\le n$</span>, and</p></li>
<li><p>If <span class="math-container">$n \lt m$</span>, then there are a much larger number, <span class="math-container">$k=\vert A\vert$</span>, of elements <span class="math-container">$g\in G$</span> where <span class="math-container">$g$</span> can only be written in at most <span class="math-container">$\frac{18^n}{2 \vert G \vert}$</span> ways as words of length <span class="math-container">$\le n$</span>.</p></li>
</ul>

<p>Here I think of <span class="math-container">$\epsilon$</span> as, say, <span class="math-container">$\frac{1}{10^9}\vert G\vert$</span>, and <span class="math-container">$k$</span> as, say <span class="math-container">$\frac{1}{10}\vert G\vert$</span>.</p>

<p>Standard universal hashing tricks create a single round Arthur-Merlin proof that the mixing time is at least <span class="math-container">$n$</span>.</p>

<ol>
<li>Arthur chooses a random element <span class="math-container">$g\in G$</span>, a random hash <span class="math-container">$h$</span> mapping words of <span class="math-container">$G$</span> onto a set of size <span class="math-container">$\frac{18^n}{\vert G \vert}$</span>, and a random image <span class="math-container">$y$</span> of <span class="math-container">$h$</span></li>
<li>Merlin tells Arthur a word <span class="math-container">$W$</span> of length up to <span class="math-container">$n$</span> that, when applied to the starting position of the cube, equals <span class="math-container">$g$</span></li>
<li>The word <span class="math-container">$W$</span> must also satisfy <span class="math-container">$h(W)=y$</span> - indicating that there are likely a <em>lot</em> of words of length <span class="math-container">$\le n$</span> that equal <span class="math-container">$g$</span></li>
<li>Arthur and Merlin repeat to amplify as needed</li>
</ol>

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

CC BY-SA 4.0
2020-04-19T19:06:00.623Z
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...)
Elle Najt
CC BY-SA 4.0
2019-03-18T23:11:26.707Z
2019-03-30T19:19:42.043Z
2019-03-30T19:19:42.043Z
Mark S
<p>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:</p>

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

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

<p>So what I believe is this is exactly a situation where we need an <em>interactive proof</em>. 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.</p>

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

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

<p>(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)</p>

<p>and the Decision problem "God's number is 20" can be restated as</p>

<p>God's number is &lt;20 <em>and</em> there exists a solution for some starting combination of the Rubik's cube which takes 20 steps.</p>

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

<p>My question is twofold </p>

<ol>
<li>Is there a actual way to do this?</li>
<li>What other examples of "pratical" uses of interactive proofs are there?</li>
</ol>

CC BY-SA 2.5
2010-11-27T02:29:21.393Z
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."
Ross Snider
CC BY-SA 2.5
2010-11-27T02:38:55.300Z
Anyway, a partial answer to your question. There is a possibly related question http://cstheory.stackexchange.com/questions/2461/interactive-proofs-for-levels-of-the-polynomial-hierarchy. 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?
Ross Snider
CC BY-SA 2.5
2010-11-27T20:18:27.267Z
@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.
gabgoh
<proofs><puzzles><interactive-proofs>
An Interactive Proof of God's Number?
gabgoh
# An Interactive Proof of God's Number?

(Asked by: username_0 on 2010-11-26)

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?

**Tags:** proofs, puzzles, interactive-proofs
> **Comments:**
> **username_1**: 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."  
> **username_1**: Anyway, a partial answer to your question. There is a possibly related question http://cstheory.stackexchange.com/questions/2461/interactive-proofs-for-levels-of-the-polynomial-hierarchy. 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?  
> **username_0**: @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.  

---

## 2 answers

### Answer by username_2 on 2010-11-27. Score: 11

> ... 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.*](http://portal.acm.org/citation.cfm?id=146585.146605) 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](http://portal.acm.org/citation.cfm?id=146609).

It was previously proved that [all IP has zero-knowledge proofs](http://www.springerlink.com/content/f2xw2nbwb2kqkewp/), so:

All languages in PSPACE have zero-knowledge interactive proofs.

> **Comments:**
> **username_3**: But proving something in $\Pi_2$ with an interactive proof generally means solving a P$^{\#\mathrm{P}}$ problem (http://cstheory.stackexchange.com/questions/2461/interactive-proofs-for-levels-of-the-polynomial-hierarchy), so if you're looking for practical interactive proofs, this won't do it.  
> **username_2**: @Peter: If by "practical" you mean the prover being BPP, then you are right. In fact, only NP languages have such proofs.  
> **username_3**: I meant by "practical" something where the prover has roughly the same computational power as the proof that God's number = 20.  
> **username_0**: 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.  
> **username_2**: @gabgoh: If deciding the problem "God's Number is < 20" lies in $\Pi_2$ you are out of luck (unless PH collapses to NP). As I said, only NP has "practical" interactive proofs. After all, if the prover cannot decide something (even after getting a short witness), he will be unable to prove it to anyone else.  
> **username_3**: @sadeq: Maybe some problems in MA and AM might, but I'm not aware of anything outside these classes which have "practical" interactive proofs.  
> **username_2**: @Peter: I don't think a polynomial-time prover can decide hard languages in either MA or AM, even if he is given any short witness. (This is true unless MA = NP or AM = NP.)  
> **username_3**: @Sadeq: MA is practical. There's a classical witness and a BPP program which checks that witness. All you need is a trusted random number generator. Second, this question was about two computers in the real world with vastly different amounts of power, so just saying that it's not in P may not be enough. I wouldn't be surprised if somebody came up with instances of graph isomorphism where there's a superpolynomial but not too impractical algorithm for distinguishing them, in which case you might have practical interactive proofs for some problems in AM.  Beyond that, I believe, is hopeless.  
> **username_2**: @Peter: You are right about MA. I didn't know why I made such stupid mistake :) As you said, "[there] might [be] practical interactive proofs for some problems in AM." Yes, and there are. In fact, since $NP \subseteq AM$, there are already such proofs. Yet unless $AM = MA$, I believe some problems in AM won't have "practical" interactive proofs.  

---

### Answer by username_4 on 2019-03-18. Score: 2

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.

> **Comments:**
> **username_5**: 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...)  

---

