Юрий Львович Притыкин
Интерактивные доказательства
Ю.Л.Притыкин планирует провести 4 занятия
Предположим, вы утверждаете, что знаете, как отличать по вкусу кока-колу от пепси-колы. Ваш друг, естественно, вам не верит и сам отличия никакого не ощущает. Какой можно было бы предложить способ, с помощью которого можно убедить друга в своей правоте, то есть в том, что вы отличать эти напитки умеете? В частности, объяснению того, как решить эту задачу, и в каком смысле, посвящён курс. Более точно, курс посвящён некоторым вводным предметам из теории сложности вычислений.
Примерная программа:
- 1. Алгоритмы, эффективные алгоритмы. Сложностные классы P (polynomial time), NP (non-deterministic polynomial time), PSPACE (polynomial space).
- 2. Вероятностные алгоритмы. Классы BPP (bounded-error probabilistic polynomial time), RP (randomized polynomial time).
- 3. Интерактивные доказательства. Классы IP (interactive proofs), AM (Arthur-Merlin).
- *4. Доказательства с нулевым разглашением. Класс ZNP (zero-knowledge proofs).
Специальных предварительных знаний не требуется. Может быть полезно (но не обязательно) знакомство с понятием вероятности (на конечных множествах). Курс начинается с краткого повторения некоторого из того, о чём более подробно рассказывалось в прошлогоднем курсе «Что такое проблема P vs. NP», но предварительного знания этого материала не требуется.
Organization Committee e-mail:
dubna@mccme.ru