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

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 135: Строка 135:
 
# Докажите, что если либо $|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$, $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$.
 
# Завершите доказательство корректности протокола большого множества, который позволяет различать случаи $|S| = a$ и $|S| = a/2$.
# Протокол большого множества можно модифицировать, чтобы если множество большое, 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$. Совет: вспомнить доказательство теоремы Лаутемана.
+
# Протокол большого множества можно модифицировать, чтобы если множество большое, 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$ (предыдущее задание).
 
# Изоморфизм графов скорее всего не является $NP$-полным. Пусть $GI \in NPC$, тогда $GNI \in coNPC$. Докажите, что из этого следует, что $\Sigma_2 = \Pi_2$. Указание: используйте факт, что для $GNI$ существует $AM$-доказательство с нулевой вероятностью ошибки, если $x \in GNI$ (предыдущее задание).
 
# Докажите, что если любой язык из $NP$ является самосводимым, то $P = NP$.
 
# Докажите, что если любой язык из $NP$ является самосводимым, то $P = NP$.

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)