1-ый вариант.

Общий вход: $ A$ - квадратная матрица большого порядка, вещественное число $ d$.

1) Первый шаг проверяющего: $ V$ преобразовывает $ A$ так, чтобы $ detA$ не изменился, применяя соответствующие свойства определителей достаточное количество раз (предполагается, что на такие преобразования у него достаточно ресурсов). Получает матрицу $ A_1$ такую, что $ detA_1=detA$. Затем преобразовывает $ A$ так, чтобы $ detA$ изменился, т.е. получает $ A_2$ такую, что $ detA_2\neq detA$. $ V$ отправляет $ A_1$ и $ A_2$ доказывающему и просит его вычислить их определители.

2) Первый шаг доказывающего: $ P$ вычисляет определители полученных матриц и отправляет их значения проверяющему.

3) Второй шаг проверяющего: $ V$ проверяет, если $ detA_1\neq d$ или $ detA_2= d$, то останавливает проверку и отвергает доказательство.

$ P$ и $ V$ повторяют шаги 1) и 3) $ m$ раз.

Проверяющий принимает доказательство, если он завершит $ m$ итераций шагов 1) - 3). В противном случае, отвергает.

2-ой вариант.

Общий вход: $ A$ - квадратная матрица большого порядка, вещественное число $ d$.

1) Первый шаг проверяющего: $ V$ наугад выбирает бит $ \alpha \in {\{0,1\}}$. Если $ \alpha=1$, то $ V$ преобразовывает $ A$ так, чтобы $ detA$ не изменился, применяя соответствующие свойства определителей достаточное количество раз (предполагается, что на такие преобразования у него достаточно ресурсов). Получает матрицу $ A_1$ такую, что $ detA_1=detA$. Если $ \alpha=0$, то $ V$ преобразовывает $ A$ так, чтобы $ detA$ изменился, т.е. получает $ A_0$ такую, что $ detA_0\neq detA$. $ V$ отправляет $ A_\alpha$ доказывающему и просит его вычислить определитель матрицы $ A_\alpha$.

2) Первый шаг доказывающего: $ P$ вычисляет определитель полученной матрицы и отправляет его значение проверяющему.

3) Второй шаг проверяющего: $ V$ проверяет, если $ detA_1\neq d$ или $ detA_2= d$, то останавливает проверку и отвергает доказательство.

$ P$ и $ V$ повторяют шаги 1) и 3) $ m$ раз.

Проверяющий принимает доказательство, если он завершит $ m$ итераций шагов 1) - 3). В противном случае, отвергает.