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

Примерная программа:

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