Интерактивное доказательство числа Бога?

В последнее время я узнал об интерактивных доказательствах, и мне было интересно, было ли все это не более чем теоретическое любопытство, или у него было какое-то практическое применение. Я думал, что начну с примера, который пришёл мне в душ:

В последнее время стало известно, что «Божье число» = 20. (Число Бога - это минимальное количество шагов, необходимых для решения кубика Рубика). Хотя это довольно интересно, кажется, есть небольшой поворот ... Это не "нормальное" доказательство в учебнике, смысл, проверяемый за полиномиальное время. Это доказательство имеет явно «грубую силу», и это означает, что парни из лаборатории доктора Морли пытались с помощью миллиардов и миллиардов комбинаций кубов в огромных суперкомпьютерах Google найти эту аккуратную, жесткую нижнюю границу.

В любом случае, вопрос таков: как мы можем быть уверены, что доктор Морли Дэвидсон и его команда честны? Ну, прямо сейчас можно выбросить аргумент от авторитета из окна, поскольку это не математически строго. Очевидная альтернатива состоит в том, чтобы повторно проверить доказательство, проверив исходный код и снова запустив все это, что кажется ужасной тратой вычислительных ресурсов, не говоря уже о том, что все, кто хотел в этом убедиться, Нужно делать это на собственной рабочей станции - очень утомительное и неприятное предложение для истинного скептика. Так что это похоже на онтологическую дилемму.

Так что я считаю, что это именно та ситуация, когда нам нужно интерактивное доказательство . Суперкомпьютер Google мог бы быть самым мощным, но обманчивым провайдером, и мы, скептически, если не анальные представители общественности, являемся ограниченными полиномами Верификаторами. Если бы мы могли каким-либо образом запрашивать наш «Оракул» полиномиальное число раз и быть уверенными в этом нижнем пределе, мы могли бы убедиться в том, что он прав, вне всякого разумного сомнения.

Таким образом, кажется, что проблема Решения «Число Бога <20» лежит в или может быть переформулирована следующим образом (неофициально)$\Pi_2^p$

Для всех начальных комбинаций в кубике Рубика существует решение, которое принимает <= 20 шагов, β, которое решает его.$\alpha$$\beta$

(не уверен, что это правильно, но и β оба малы по размеру, учитывая начальную конфигурацию и решение, легко проверить, действительно ли он решает куб)$\alpha$$\beta$

и решение проблемы "число Бога 20" можно переформулировать как

Число Бога <20, и существует решение для некоторой стартовой комбинации кубика Рубика, которая занимает 20 шагов.

Так что, вероятно, для этого есть IP [n] доказательство. (еще раз, проверьте мою работу)

Мой вопрос двоякий

1. Есть ли реальный способ сделать это?
2. Какие еще примеры «практического» использования интерактивных доказательств есть?

$\Pi_2^p$

$\rm{PH} \subseteq P^{\#P}$$L\in \rm{PH}$

Используя свои приемы, Шамир доказал, что IP = PSPACE .

Ранее было доказано, что все IP имеют доказательства с нулевым разглашением , поэтому:

Все языки в PSPACE имеют интерактивные доказательства с нулевым знанием.

$20$$G$$s=\langle U, U', U^2, D, D', D^2,\cdots\rangle$$m$$\epsilon$$\pi$

$n\lt m$$n\ge m$$\pi$$A\subset G$ $\mathsf{AM}$

$\vert s \vert=18$$m$

• $n\ge m$$\epsilon$$g\in G$$\frac{18^n}{\vert G \vert}$$g$$s$$\le n$

• $n \lt m$$k=\vert A\vert$$g\in G$$g$$\frac{18^n}{2 \vert G \vert}$$\le n$

$\epsilon$$\frac{1}{10^9}\vert G\vert$$k$$\frac{1}{10}\vert G\vert$

$n$

1. $g\in G$$h$$G$$\frac{18^n}{\vert G \vert}$$y$$h$
2. $W$$n$$g$
3. $W$$h(W)=y$$\le n$$g$
4. Артур и Мерлин повторяют для усиления по мере необходимости

Поскольку для групп, я думаю, время смешивания составляет, по крайней мере, диаметр (число Бога), это также обеспечивает доказательство Артура-Мерлина для ограничения числа Бога в большой группе.