Изменения
Нет описания правки
# Часть 3. Рассмотрим $\mathrm{perm}(D_A(x))$. Докажите, что он является полиномом от $x$. Какой степени?
# Часть 4. На основании предыдущих трех заданий и конструкции интерактивного доказательства для $\#SAT$ разработайте интерактивное доказательство для языка $\langle A, k\rangle$, где $\mathrm{perm}A = k$.
# Докажите, что следующая конструкция является универсальным семейством попарно независимых хеш-функций $\mathbb{B}^n \to \mathbb{B}^k$. Рассмотрим все матрицы $A$ размера $k \times n$ из нулей и единиц, а также все вектора длины $k$. Все вычисления выполняются по модулю 2. Для каждой пары матрицы-вектор определим хеш-функцию $h(x) = Ax+b$.
# Докажите, что если $S \subset \mathbb{B}^n$, $h$ случайно равновероятно выбрана из универсального семейства попарно независимых хеш функций, $\mathbb{B}^n \to \mathbb{B}^k$, $|S| \le 2^{k-1}$, $p = |S|/2^k$, $y$ выбран случайно равновероятно из множества $\mathbb{B}^k$, то $3p/4\le \mathbb{P}(\exists x\in S: h(x)=y)\le p$.
# Докажите, что если либо $|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}$, (обозначение $|_{<n}$ означает, что все вопросы к оракулу имеют длину строго меньше $n$, где $n$ - длина входа). Докажите, что $SAT$ является самосводимым.
# Докажите, что если $L$ самосводим, то $L \in PSPACE$.
# Докажите, что язык $GI$ пар изоморфных графов является самосводимым.
# Докажите, что для языка $GI$ пар изоморфных графов можно, используя самосводимость, за полиномиальное время восстановить перестановку изоморфизма.
