На главную страницу ЛШСМ-2009 К списку курсов ЛШСМ-2009

Юрий Львович Притыкин

Интерактивные доказательства

Ю.Л.Притыкин планирует провести 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», но предварительного знания этого материала не требуется.


Rambler's Top100