Изменения

# Рассмотрим следующее (неверное) доказательство, что $NP \subset BPP$. Решим для этого $NP$-полную задачу $CIRCUIT-SAT$. Рассмотрим булеву схему в базисе "$\oplus$", "$\wedge$", "$\mathbb{1}$". Превратим её в арифметическую схему, заменив элемент "$\oplus$" на "$+$", а "$\wedge$" на "$\times$". Теперь проверим её на вычисление тождественного нуля с помощью предыдущей задачи. В чём ошибка в рассуждениях?

# Вероятностный Prover. Докажите, что возможность использовать (свою, отличную от ленты Verifier) вероятностную ленту для Prover не меняет множество языков из $IP$.

# Интерактивное доказательство для перманента, часть 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$. Какой степени?