Изменения

# Докажите, что язык $GI$ пар изоморфных графов является самосводимым.

# Докажите, что для языка $GI$ пар изоморфных графов можно, используя самосводимость, за полиномиальное время восстановить перестановку изоморфизма.

# Докажите, что следующая конструкция является универсальным семейством попарно независимых хеш-функций $\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$.

# Протокол большого множества можно модифицировать, чтобы если множество большое, Prover мог добиться, чтобы Verifier принимал с вероятностью 1. Из каких компонент сложить решение: пусть $S \subset \mathbb{B}^n$, $|S| = a$ или $|S| = a/c$, где $c$ - параметр, который выберем позже, $H$ - универсальное семейство попарно независимых хеш-функций из $\mathbb{B}^n$ в $\mathbb{B}^k$. Можно выбрать такое $c$ и такое $t$, полиномиальное от $n$, что если $|S| = a$, то существуют $t$ хеш-функций $h_1, \ldots, h_t$, что $\cup h_i(S) = \mathbb{B}^k$, а если $|S| = a/c$, то для любых $t$ хеш-функций $|\cup h_i(S)| < 2^{k-1}$. При этом $c$ можно менять, рассматривая вместо $S$ множество $S^z$ для целого $z$. Совет: вспомнить доказательство теоремы Лаутемана.

# Изоморфизм графов скорее всего не является $NP$-полным. Пусть $GI \in NPC$, тогда $GNI \in coNPC$. Докажите, что из этого следует, что $\Sigma_2 = \Pi_2$. Указание: используйте факт, что для $GNI$ существует $AM$-доказательство с нулевой вероятностью ошибки, если $x \in GNI$ (предыдущее задание).