2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Неявные доказательства
Сообщение08.12.2020, 22:32 
Аватара пользователя


13/08/13

4323
Как называется вещь, когда мы может доказать, что у нас есть какое-то построение, ключ и т.д. без предъявления этого самого построения? Я просто забыл название - неявные доказательства или как-то по другому?
Помню читал одну статью, там в качестве примера приводилась раскраска плоскости двумя цветами с определенным условием, и что дескать можно проверить, есть ли у вас эта раскраска без предоставления какой-либо информации о реальных цветах в вашей раскраске.

 Профиль  
                  
 
 Re: Неявные доказательства
Сообщение08.12.2020, 22:35 


05/09/16
11533
Неконструктивное

Sicker в сообщении #1495780 писал(а):
Неа, это вообще не о виде доказательства.

Откройте википедию и почитайте.

 Профиль  
                  
 
 Re: Неявные доказательства
Сообщение08.12.2020, 22:42 
Аватара пользователя


13/08/13

4323
wrest
Неа, это вообще не о виде доказательства. Это о проверке, есть ли у вас доказательство, или нет

 Профиль  
                  
 
 Re: Неявные доказательства
Сообщение08.12.2020, 23:10 
Заслуженный участник
Аватара пользователя


16/07/14
8464
Цюрих
Доказательство с нулевым разглашением?

 Профиль  
                  
 
 Re: Неявные доказательства
Сообщение08.12.2020, 23:37 
Аватара пользователя


13/08/13

4323
mihaild в сообщении #1495781 писал(а):
Доказательство с нулевым разглашением

Точно! :D

 Профиль  
                  
 
 Re: Неявные доказательства
Сообщение09.12.2020, 00:25 


22/10/20
1061
В википедии в статье "Доказательство с нулевым разглашением" в пункте "Пещера нулевого разглашения" приводится пример с Пегги, Виктором и пещерой.
Википедия писал(а):
В данном случае Пегги выступает в качестве Доказывающего утверждение, и Виктор — в качестве Проверяющего (в англоязычной литературе обычно используются наименование сторон Peggy от «Prover» и Victor от «Verifier»). Пегги знает магическое слово («ключ»), ввод которого позволяет открыть ей дверь между C и D. Виктор хочет узнать, действительно ли Пегги знает пароль, при этом Пегги не хочет выдавать сам пароль. Пещера имеет круглую форму, как представлено на рисунке. Для того чтобы решить проблему, они поступают следующим способом. Пока Виктор находится в точке А, Пегги идёт к двери, и после того, как она исчезает из виду, Виктор идёт к разветвлению, то есть в точку B, и кричит оттуда: «Пегги нужно выйти справа» или «Пегги нужно выйти слева». Получаем каждый раз вероятность того, что Пегги не знает пароль, равна 50 %.
А почему бы просто не попросить Пегги зайти в пещеру справа и выйти слева (или наоборот, в зависимости от того, куда открывается дверь)? Или тут имеется в виду, что в этом случае будет использоваться дополнительная информация, в какую сторону открывается дверь, которую по условию Пегги не хочет раскрывать?

 Профиль  
                  
 
 Re: Неявные доказательства
Сообщение09.12.2020, 00:29 
Аватара пользователя


13/08/13

4323
EminentVictorians
Конечно, можно сделать проще :-) Весь смысл просто в демонстрации принципа док-ва с нул. разглашением

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Mikhail_K


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group