1632
правки
Изменения
м
rollbackEdits.php mass rollback
# Докажите, что если существует язык $L \in NEXPC \cap EXP$, то $NEXP = EXP$.
# Пусть задан язык $L$, принадлежащий $NP$. Зафиксируем проверку сертификатов $R(x, y)$. Обозначим как $c(x)$ число сертификатов, которые подходят для данного $x$ (очевидно, если $x \not\in L$, то $c(x) = 0$, а если $x \in L$, то $c(x) \ge 1$). Сведение по Карпу $f$ одного языка к другому, для каждого из которых зафиксирована проверка сертификатов, называется честным (англ. parsimonious), если оно сохраняет $c$, то есть $c(f(x)) = c(x)$. Докажите, что сведение $BH_{1N}$ к $SAT$ в теореме Кука является честным, если в качестве сертификата использовать последовательность недетерминированных выборов, приводящих машину Тьюринга из входа для $BH_{1N}$ к допуску.
# Эффективная BGS. Докажите, что существует язык $B \in EXP$, такой что $P^B\ne NP^B$.
# Докажите, что $DSPACE(n) \ne NP$.
# Формальная система доказательств представляет собой способ записи утверждений, аксиом, правила вывода и способ записи доказательств. Будем считать, что рассматривается достаточно богатая формальная система, в которой можно записывать различные утверждения про программы. Докажите, что язык $\{\langle \varphi, 1^n\rangle|\varphi$ - верное утверждение, имеющее доказательство длиной не больше $n\}$ является $NP$-трудным. Какие свойства надо предъявить к формальной системе, чтобы он являлся $NP$-полным?
# Петя свёл язык $A$ по Карпу к $NP$-полному языку $B$. Учитель утверждает, что из этого не следует, что $A$ является $NP$-полным. Помогите учителю подобрать пример.
# Предположим, что существует $NP$-полный язык, для которого существует решение за $O(n^{C\log_2n})$, где $C$ - константа. Что можно сказать про класс $NP$ в этом случае?
# Верно ли, что если $A \le B$, то $A \in P^B$? В случае, если вы не можете доказать свой ответ, можно привести разумные аргументы в его пользу.
# Верно ли, что если $A \in P^B$, то $A \le B$? В случае, если вы не можете доказать свой ответ, можно привести разумные аргументы в его пользу.
# Сережа дал такое определение $NP$-полноты: язык $L$ является $NP$-полным по Серёже, если $L \in P \Rightarrow P = NP$. Прокомментируйте определение Серёжи.
# Юра дал такое определение класса $NP$: это задачи, который можно решить перебором. Прокомментируйте определение Юры.
# Докажите, что найдется такой оракул $A$ и язык $L \in NP^A$, что $L$ не сводится к $3SAT$ за полином даже, если у сведения есть доступ к оракулу для $A$.
# Докажите, что если $L\in coNP$, то $L^* \in coNP$.
# Покажите, что $TQBF$ является $PS$-трудной даже для $LOG-Space$ сведений.
# Может ли выполняться $TQBF\in L$?
# Может ли выполняться $TQBF\in NL$?
# Разработайте алгоритм, который по матрице смежности графа выводит его матрицу инцидентности, используя $O(\log V)$ дополнительной памяти, где $V$ --- количество вершин графа.
# Разработайте алгоритм проверки, является ли неориентированный граф, заданный списками смежности, ациклическим, используя $O(\log V)$ дополнительной памяти, где $V$ --- количество вершин графа. Алгоритм должен быть детерминированным.
# Разработайте недетерминированный алгоритм проверки, является ли ориентированный граф, заданный списками смежности, ациклическим, используя $O(\log V)$ дополнительной памяти, где $V$ --- количество вершин графа.
# Докажите, что $2SAT \in NL$
# $BH_{1N}$ является $NP$-полным. Определите по аналогии $P$-полный язык.
# Определим $polyL$ как $\cup_{c>0}DSPACE(\log^c n)$. $PATH = \{\langle G, s, t\rangle,$ в ориентированном графе $G$ есть путь из $s$ в $t\}$. Докажите, что $PATH \in polyL$.
# Определим $SC$ (расшифровывается как Stephen's Class в честь Стивена Кука) как класс языков, для которых существует программа, которая ''одновременно'' удовлетворяет ограничениям для $polyL$ и $P$. Неизвестно, принадлежит ли $PATH$ классу $SC$. Поясните, почему доказательство из предыдущего задания не подходит для $SC$.
# Обозначим как $DP$ множество языков $L$, для которых найдутся $L_1 \in NP$ и $L_2 \in coNP$, такие что $L = L_1 \cap L_2$. Докажите, что $NP \subset DP$.
# Будем считать, что $NP \ne coNP$, верно ли, что $coNP \subset DP$?
# Рассмотрим язык $EXACTINDSET = \{\langle G, k\rangle | \text{ максимальное}$ $\text{независимое множество в графе $G$ имеет размер $k$}\}$. Докажите, что $EXACTINDSET$ является полным для класса $DP$ относительно полиномиального сведения.
# Докажите, что если $\Sigma_i = \Pi_i$, то $\Sigma_{i} = \Sigma_{i+1}$.
# Докажите, что $\Sigma_{i+1} = NP^{\Sigma_i}$.
# Задайте $\Pi_{i+1}$ через классы $i$-го уровня $PH$ на языке оракулов.
# Докажите, что если $P = NP$, то $P = PH$.
# Докажите, что если если у $PH$ существует полный относительно сведения по Карпу за полином язык, то $PH = \Sigma_i$ для некоторого $i$.
# Докажите, что если $PH = PS$, то $PH = \Sigma_i$ для некоторого $i$.
# Докажите, что если $P^A = NP^A$, то $PH^A \subset P^A$.
# Докажите, что $EXACTINDSET \in \Sigma_2 \cup \Pi_2$. Сделайте вывод про место $DP$ в полиномиальной иерархии.
# Адаптируйте доказательство теоремы Фортноу $SAT \not\in TISP(n^c, n^d)$ для любых $c$ и $d$ где $c(c+d) < 2$.
# Докажите, что задача $CIRCSAT$ о проверке удовлетворимости булевой схемы из функциональных элементов является $NP$-полной.
# Предложите разрешимый язык из $P/poly$, который не лежит в $P$.
# Докажите, что $Sparse \subset P/poly$ ($Sparse$ - множество языков, которые имеют лишь полиномиальное число слов каждой длины).
# Докажите, что для любого $k > 0$ в $PH$ найдется язык, со схемной сложностью $\Omega(n^k)$.
# Докажите, что для любого $k > 0$ в $\Sigma_2$ найдется язык, со схемной сложностью $\Omega(n^k)$.
# Докажите, что существует язык из $DSPACE(2^{O(n)})$, которой не принадлежит $SIZE(2^{o(n)})$.
# Докажите, что если $EXP \subset P/poly$, то $EXP = \Sigma_2$.
# Докажите, что если $P=NP$, то в $EXP$, есть язык со схемной сложностью $\Omega(2^n/n)$.
# Докажите, что умножение булевых матриц лежит в $NC$ (иначе говоря, существует схема глубиной $\log^k(n)$ для умножения матриц $n \times n$ для некоторой константы $k$).
# Выведите из предыдущего задания, что $PATH \in NC$.
# Выведите из предыдущего задания, что $NL \subset NC$.
# Докажите, что $NC^1 \subset L$ ($L$ здесь log space).
# Альтернативное определение $ZPP$. Докажите, что $L \in ZPP$ тогда и только тогда, когда существует вероятностная программа $p$, которая работает за полиномиальное время, выдает 0 1 или 2, если она выдает 0 или 1, то это значение равно $x \in L$, а 2 ("не знаю") возвращается с вероятностью не больше 1/2.
# Докажите, что $ZPP = RP \cap coRP$.
# Докажите, что $BPP \subset PS$.
# Докажите, что $RP \subset NP$.
# Обозначим как $PP^+$ как класс языков, для которых существует вероятностная программа $M$, работающая за полином, что если $x \in L$, то $P(M(x) = 1) > 1/2$, а если $x \notin L$, то $P(M(x) = 0) \ge 1/2$. Докажите, что $PP^+ = PP$.
# Докажите, что $NP \subset PP$.
# Докажите, что если для $L$ найдется программа $M$ с полиномиальным временем работы и полином $p > 0$, такие что $P(M(x) = [x \in L]) \ge \frac{1}{2} + \frac{1}{p(|x|)}$, то $L \in BPP$.
# Докажите, что если $L \in BPP$, то для любого полинома $p > 1$ найдется программа $M$ с полиномиальным временем работы, такая что $P(M(x) = [x \in L]) \ge 1 - 2^{-p(|x|)}.$
# Определим класс $RL$ как класс языков $L$, для которых найдется вероятностная программа $M$, использующая $O(\log n)$ дополнительной памяти, такая что если $x \in L$, то $P(M(x) = 1) \ge 1/2$, если $x \notin L$, то $P(M(x) = 1) = 0$. Докажите, что $RL \subset P$
# Докажите, что задача проверки того, что в неориентированном графе есть путь из $s$ в $t$, лежит в $RL$.
# Почему решение предыдущей задачи не удается распространить на ориентированные графы?
# Докажите, что если $NP \subset BPP$, то $NP = RP$.
# В определении $ZPP$ нет требования, чтобы на любой вероятностной ленте программа завершалась. Докажите, что если добавить это ограничение, определение класса $ZPP$ не поменяется.
# При симуляции $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$.
# Докажите, что $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$?
