Редактирование: Доказательства с нулевым разглашением

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 9: Строка 9:
 
Пусть <tex>L</tex> ∈ '''[[NP]]''', и <tex>M</tex> — машина Тьюринга для проверки сертификата, то есть <tex>x \in L \Leftrightarrow \exists y \in \{0,1\}^{p(|x|)} : M(x, y) = 1</tex>. Пара <tex>\langle P, V \rangle</tex> интерактивных вероятностных алгоритмов называется доказательством с нулевым разглашением для <tex>L</tex>, если выполнены следующие три условия:
 
Пусть <tex>L</tex> ∈ '''[[NP]]''', и <tex>M</tex> — машина Тьюринга для проверки сертификата, то есть <tex>x \in L \Leftrightarrow \exists y \in \{0,1\}^{p(|x|)} : M(x, y) = 1</tex>. Пара <tex>\langle P, V \rangle</tex> интерактивных вероятностных алгоритмов называется доказательством с нулевым разглашением для <tex>L</tex>, если выполнены следующие три условия:
 
# '''Полнота''': Для любого <tex>x \in L</tex> и сертификата <tex>y</tex> выполнено <tex>P \left( \text{out}_V \left\langle P(x,y), V(x) \right\rangle = 1 \right) \ge 2/3</tex>
 
# '''Полнота''': Для любого <tex>x \in L</tex> и сертификата <tex>y</tex> выполнено <tex>P \left( \text{out}_V \left\langle P(x,y), V(x) \right\rangle = 1 \right) \ge 2/3</tex>
# '''Корректность''': Если <tex>x \not \in L</tex>, то для любых <tex>P^*, y</tex> выполнено <tex> P \left( \text{out}_V \left\langle P^*(x,y), V(x) \right\rangle = 1 \right) \le 1/3</tex>
+
# '''Корректность''': Если ''x'' ∉ ''L'', то для любых <tex>P^*, y</tex> выполнено <tex> P \left( \text{out}_V \left\langle P^*(x,y), V(x) \right\rangle = 1 \right) \le 1/3</tex>
# '''Нулевое разглашение''': Для любой вероятностной полиномиальной интерактивной стратегии <tex>V^*</tex> существует вероятностный полиномиальный алгоритм <tex>S^*</tex>, такой что для любого <tex>x \not \in L</tex> и соответствующего сертификата ''y'' выполнено <tex>\text{out}_{V^*} \left \langle P(x,y), V^*(x) \right \rangle\equiv S^*(x)</tex>. Такой алгоритм <tex>S^*</tex> называется симулятором для <tex>V^*</tex>, он симулирует результат взаимодействия <tex>V^*</tex> c proover'ом без доступа к последнему.
+
# '''Нулевое разглашение''': Для любой вероятностной полиномиальной интерактивной стратегии <tex>V^*</tex> существует вероятностный полиномиальный алгоритм <tex>S^*</tex>, такой что для любого ''x'' ∈ ''L'' и соответствующего сертификата ''y'' выполнено <tex>\text{out}_{V^*} \left \langle P(x,y), V^*(x) \right \rangle\equiv S^*(x)</tex>. Такой алгоритм <tex>S^*</tex> называется симулятором для <tex>V^*</tex>, он симулирует результат взаимодействия <tex>V^*</tex> c proover'ом без доступа к последнему.
  
 
== Пример: изоморфизм графов ==
 
== Пример: изоморфизм графов ==

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

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

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