Изменения
Нет описания правки
# Арифметическая схема - аналог булевой схемы, но на вход она получает $m$-битные неотрицательные целые числа, а вместо функциональных элементов используются арифметические: "$+$", "$-$" и "$\times$". Также на некоторые входы разрешается подать константы. Все вычисления происходят в целых числах. Разработайте вероятностный алгоритм проверки, что заданная арифметическая схема с $n$ арифметическими элементами равна нулю на любых входах, полиномиальный относительно $n$ и $m$.
# Рассмотрим следующее (неверное) доказательство, что $NP \subset BPP$. Решим для этого $NP$-полную задачу $CIRCUIT-SAT$. Рассмотрим булеву схему в базисе "$\oplus$", "$\wedge$", "$\mathbb{1}$". Превратим её в арифметическую схему, заменив элемент "$\oplus$" на "$+$", а "$\wedge$" на "$\times$". Теперь проверим её на вычисление тождественного нуля с помощью предыдущей задачи. В чём ошибка в рассуждениях?
# Вероятностный Prover. Докажите, что возможность использовать (свою, отличную от ленты Verifier) вероятностную ленту для Prover не меняет множество языков из $IP$.
# Запрет на обман. Докажите, что если установить требование, что для слов из языка вероятность допуска равна 0, то получившийся класс $IP_0 = NP$.
# Интерактивное доказательство для перманента, часть 1. Перманент матрицы - $\mathrm{perm}(A)=\sum_{\sigma}\prod_{i=1}^n a_{i\sigma_i}$ - вычисляется по той же формуле, что и определитель, но суммирование происходит без $(-1)^{\mathrm{sign}(\sigma)}$. Можно показать, что вычисление перманента - трудная задача. Докажите формулу разложения перманента по первой строке $\mathrm{perm}(A)=\sum_{i=1}^n a_{1i}\mathrm{perm}(A_{1i})$.
# Часть 2. Рассмотрим $A_{1i}[j][k]$ как функцию от $i$. Докажите, что для всех $j$ и $k$ она является полиномом от $i$. Какой степени? Рассмотрим матрицу полиномов $D_A(x)$, элемент которой $D_A(x)[j][k]$ для всех $i$ равен $A_{1i}[j][k]$
# Часть 3. Рассмотрим $\mathrm{perm}(D_A(x))$. Докажите, что он является полиномом от $x$. Какой степени?
# Часть 4. На основании предыдущих трех заданий и конструкции интерактивного доказательства для $\#SAT$ разработайте интерактивное доказательство для языка $\langle A, k\rangle$, где $\mathrm{perm}A = k$.
