Изменения

Перейти к: навигация, поиск

Список заданий по теории сложности 2020

1 байт убрано, 14:11, 1 июня 2020
Нет описания правки
# Докажите, что если либо $|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$ пар изоморфных графов является самосводимым.
Анонимный участник

Навигация