Изменения
Нет описания правки
# При симуляции $random(n)$ с помощью бросков честной монеты (или абстракции вероятностной ленты) математическое ожидание времени работы $random(n)$ равно $O(\log n)$, но нет ограничения сверху на число бросков. Кажется, что это может испортить определение классов $RP$ или $BPP$, потому что в них время работы программы должно быть ограничено сверху. Докажите, что это не так и можно разрешить конструкции $random(n)$ в вероятностных программах из определения $RP$ или $BPP$, даже если на самом деле в модели вычислений есть доступ к источнику случайности только с распределением честной монеты.
# Нечестные монеты с нерациональным $p$ могут привести к парадоксам. Докажите, что существует такое $p$, такой неразрешимый язык $L$ и такая программа $A$, что если у программы $A$ есть доступ к источнику случайности с распределением нечестной монеты с вероятностью выпадения $1$ равной $p$, то она может распознать язык $L$ за полиномиальное время.
# Полные языки для $BPP$. Будем называть $A\in BPP$ язык полным для $BPP$, если для любого языка $B \in BPP$ выполнено $B \le A$. Петя предполагает, что язык $BH_{1DP} = \{\langle p, x, 1^t \rangle\}$, где $p$ — вероятностная программа, допускающая $x$ за время $t$ с вероятностью не меньше $2/3$ является полным для $BPP$. Прав ли Петя?
# Вероятностные сведения. Будем говорить, что $B$ вероятностно сводится к $C$ и писать $B \le_r C$, если найдется такая вероятностная программа $p$, работающая за полином, что $P([x \in B] = [p(x) \in C]) \ge 2/3$. Докажите, что если $C \in BPP$, $B \le_r C$, то $B \in BPP$.
# Докажите, что $\le_r$ не является транзитивным отношением.
# Класс $BP\cdot NP$ определяется как множество $\{A | A \le_r 3SAT\}$. Докажите, что $NP \subset BP\cdot NP$.
# Докажите, что $BPP \subset BP\cdot NP$.
# Определим язык $UNIQUE-SAT$ как множество удовлетворимых булевых формул, которые имеют единственное удовлетворяющее назначение. Докажите, что $UNIQUE-SAT \in BP\cdot NP\subset \Sigma_3$.
# Докажите, что если $\overline{3SAT} \subset BP\cdot NP$, то $PH = \Sigma_3$.
# Определим класс $BPL$ как класс языков $L$, для которых найдется вероятностная программа $M$, использующая $O(\log n)$ дополнительной памяти, такая что если $P(M(x) = [x \in L]) \ge 2/3$. Докажите, что $BPL \subset P$.
# Докажите, что $BPL \subset SC$.
# Загадано неотрицательное целое число $a \le 2^{2^n}$. Оракул умеет отвечать на вопрос $q(k) = a \bmod k$. Разработайте вероятностный алгоритм проверки, что $a = 0$, полиномиальный относительно $n$.
# Арифметическая схема - аналог булевой схемы, но на вход она получает $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$. Какой степени?
# Часть 3. Рассмотрим матрицу полиномов $D_A(x)$, элемент которой $D_A(x)[j][k]$ для всех $i$ равен $A_{1i}[j][k]$. Рассмотрим $\mathrm{perm}(D_A(x))$. Докажите, что он является полиномом от $x$. Какой степени?
# Часть 4. На основании предыдущих трех заданий и конструкции интерактивного доказательства для $\#SAT$ разработайте интерактивное доказательство для языка $\langle A, k\rangle$, где $\mathrm{perm}A = k$.
# Назовём язык $L$ самосводимым, если $L \in P^{L^{<n}}$, (обозначение $L^{<n}$ означает, что все вопросы к оракулу имеют длину строго меньше $n$, где $n$ - длина входа). Докажите, что $SAT$ является самосводимым.
# Докажите, что если $L$ самосводим, то $L \in PSPACE$.
# Докажите, что язык $GI$ пар изоморфных графов является самосводимым.
# Докажите, что для языка $GI$ пар изоморфных графов можно, используя самосводимость, за полиномиальное время восстановить перестановку изоморфизма.
# Докажите, что любой язык из $NPC$ является самосводимым.
# Следует ли из доказательства предыдущего задания, что для любого языка $L \in NPC$ и функции проверки сертификатов $R(x, y)$ при условии доступа к оракулу для $L^{<n}$ можно по $x$ за полиномиальное время построить сертификат $y$?
