Uma prova interativa do número de Deus?

Ultimamente, tenho aprendido sobre provas interativas e me pergunto se tudo não passava de uma curiosidade teórica ou se havia alguma aplicação prática. Pensei em começar com um exemplo que me ocorreu no chuveiro:

Ultimamente, tem divulgado que "Número de Deus" = 20. (O número de Deus é o número mínimo de etapas necessárias para resolver o cubo de Rubik). Embora isso seja bastante interessante, parece haver uma pequena reviravolta ... Essa não é uma prova "normal" no livro, sentido verificável pelo tempo polinomial. Essa prova tem um sabor distintamente de "força bruta" - com isso quero dizer, os caras do laboratório do Dr. Morley tentaram com bilhões e bilhões de combinações de cubos nos enormes supercomputadores do Google a encontrar esse limite mais baixo e limpo.

Enfim, a pergunta é: como podemos ter certeza de que o Dr. Morley Davidson e sua equipe são honestos? Bem, imediatamente pode jogar fora o argumento da autoridade, pois não é matematicamente rigoroso. A alternativa óbvia é verificar novamente a prova, verificando o código-fonte e executando tudo novamente, o que parece ser um terrível desperdício de recursos computacionais, sem mencionar o fato de que todos que desejarem se convencer disso, precisa fazê-lo em sua própria estação de trabalho - uma proposta muito tediosa e desagradável para o verdadeiro cético. Portanto, isso parece ser um tipo de deilema ontológico.

Então, o que eu acredito é que essa é exatamente uma situação em que precisamos de uma prova interativa . O supercomputador do Google poderia ser o Provador todo poderoso, mas enganoso, e nós, os céticos, se não os analistas do público, somos os Verificadores Polinomialmente limitados. Se, de alguma forma, pudéssemos consultar nosso "Oracle" um número polinomial de vezes e nos convencer desse limite inferior, poderíamos estar convencidos do fato de que ele está certo, além de qualquer dúvida razoável.

Parece que o problema de decisão "O número de Deus é <20" está em ou pode ser atualizado da seguinte maneira (informalmente)$\Pi_2^p$

Para todas as combinações iniciais no Cubo de Rubik, existe uma solução que leva <= 20 etapas, que a resolve.$\alpha$$\beta$

(não tenho certeza se isso está correto, mas e são pequenos em tamanho, dada uma configuração inicial e uma solução, é fácil verificar se ele realmente resolve o cubo)$\alpha$$\beta$

e o problema de decisão "número de Deus é 20" pode ser corrigido como

O número de Deus é <20 e existe uma solução para alguma combinação inicial do cubo de Rubik, que leva 20 etapas.

Portanto, provavelmente há uma prova de IP [n] para isso. (mais uma vez, verifique meu funcionamento)

Minha pergunta é dupla

1. Existe uma maneira real de fazer isso?
2. Que outros exemplos de usos "práticos" de provas interativas existem?

... parece que o problema da decisão "O número de Deus é <20" está em .$\Pi_2^p$

Isso é suficiente para ter uma prova interativa. De fato, Lund et al. provou que todo idioma na hierarquia polinomial (PH) tem uma prova interativa usando o teorema de Toda ( ). Eles reduziram para a linguagem P-completa PERMANENT e forneceram um método algébrico que pode ser usado para provar PERMANENTE interativamente. (Isso é altamente impreciso; consulte o documento para obter mais informações.) L ∈ P $\rm{PH} \subseteq P^{\#P}$$L\in \rm{PH}$

Usando suas técnicas, Shamir provou que IP = PSPACE .

Foi provado anteriormente que todo IP possui provas de zero conhecimento , portanto:

Todos os idiomas do PSPACE têm provas interativas de conhecimento zero.

Determinando que é o diâmetro (número de Deus) do Grupo do Cubo de Rubik sob a métrica de meia volta com o conjunto de geradores Singmaster foi um resultado maravilhoso. Estou curioso sobre questões de acompanhamento, tais como determinar quantas voltas meia volta que seria necessário para obter o cubo totalmente "misto" para -close à distribuição estacionária uniforme . $20$$G$$s=\langle U, U', U^2, D, D', D^2,\cdots\rangle$$m$$\epsilon$$\pi$

Acredito que essa mistura exibe um ponto de corte em que, para , algumas configurações são muito mais prováveis ​​que outras, enquanto que para o cubo é quase totalmente embaralhado na distribuição uniforme , e nenhum grande subconjunto de configurações é desfavorecido. Pode haver uma promessa no coração de qualquer mistura que mostre tal corte. Essa promessa pode ser aproveitada para criar um protocolo Arthur-Merlin .$n\lt m$$n\ge m$$\pi$$A\subset G$A M $\mathsf{AM}$

Por exemplo, observando que e chamando do para-ser-verificado tempo de mistura, acho que posso prometer:$\vert s \vert=18$$m$

• Se então, com exceção de um número muito pequeno, , dos elementos há muito perto de maneiras de escrever como palavras em de comprimento , e$n\ge m$$\epsilon$$g\in G$$\frac{18^n}{\vert G \vert}$$g$$s$$\le n$

• Se , existe um número muito maior, , de elementos onde só pode ser escrito no máximo maneiras como palavras de comprimento .$n \lt m$$k=\vert A\vert$$g\in G$$g$$\frac{18^n}{2 \vert G \vert}$$\le n$

Aqui penso em como, digamos, , e como, digamos .$\epsilon$$\frac{1}{10^9}\vert G\vert$$k$$\frac{1}{10}\vert G\vert$

Os truques universais de hash universal criam uma única prova redonda de Arthur-Merlin de que o tempo de mistura é pelo menos .$n$

1. Arthur escolhe um elemento aleatório , um hash aleatório palavras de mapeamento de para um conjunto de tamanho , e uma imagem aleatória de$g\in G$$h$$G$$\frac{18^n}{\vert G \vert}$$y$$h$
2. Merlin diz a Arthur uma palavra de comprimento até que, quando aplicada à posição inicial do cubo, é igual a$W$$n$$g$
3. A palavra também deve satisfazer - indicando que provavelmente há muitas palavras de comprimento iguais a$W$$h(W)=y$≤ n g$\le n$$g$
4. Arthur e Merlin repetem para amplificar conforme necessário

Porque, para os grupos que penso, o tempo de mistura é pelo menos o diâmetro (número de Deus), isso também fornece uma prova de Arthur-Merlin para limitar o número de Deus de um grande grupo.