Изменения
Нет описания правки
# Докажите, что если либо $|S| = a$, либо $|S| = a/2$, $k$ равно минимальному целому числу, для которого $a \le 2^{k-1}$, то существуют различные константы $c_1 < c_2$, такие что выполнено следующее. Если $h$ случайно равновероятно выбрана из универсального семейства попарно независимых хеш функций, $\mathbb{B}^n \to \mathbb{B}^k$, $y$ выбран случайно равновероятно из множества $\mathbb{B}^k$, то если $|S| = a$, то $\mathbb{P}(\exists x\in S: h(x)=y)\ge c_2$, а если $|S| = a/2$, то $\mathbb{P}(\exists x\in S: h(x)=y)\le c_1$.
# Завершите доказательство корректности протокола большого множества, который позволяет различать случаи $|S| = a$ и $|S| = a/2$.
# Назовём язык $L$ самосводимым, если $L \in P^{L|^{<n}}$, (обозначение $|L^{<n}$ означает, что все вопросы к оракулу имеют длину строго меньше $n$, где $n$ - длина входа). Докажите, что $SAT$ является самосводимым.
# Докажите, что если $L$ самосводим, то $L \in PSPACE$.
# Докажите, что язык $GI$ пар изоморфных графов является самосводимым.
# Докажите, что для языка $GI$ пар изоморфных графов можно, используя самосводимость, за полиномиальное время восстановить перестановку изоморфизма.
# Докажите, что любой язык из $NP$ является самосводимым.
# Следует ли из доказательства предыдущего задания, что для любого языка $L \in NP$ и функции проверки сертификатов $R(x, y)$ при условии доступа к оракулу для $L|^{<n}$ можно по $x$ за полиномиальное время построить сертификат $y$?
