Изменения
Нет описания правки
# Докажите, что найдется такой оракул $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$.
# Докажите, что $L = NC^1$ ($L$ здесь log space).
