Сложность вычислений — 2

Дата публикации

14 сентября 2026

Паспорт

  • Статус названия. В официальном плане 01.03.02 для набора 2025 нет самостоятельной дисциплины с названием «Сложность вычислений — 2».
  • Ближайшая подтверждённая дисциплина. В VI семестре есть выборный курс «Сложность вычислений: дополнительные главы»: 45 часов, 1 з.е., 30 аудиторных часов (15 лекций, 15 семинаров) и 15 часов самостоятельной работы.
  • Кафедра и преподаватель. В открытом плане специализация — дискретная математика; преподаватель для этого варианта не указан.
  • Итоговый контроль. Для выборного курса форма контроля в извлечённом фрагменте плана не идентифицируется однозначно; нужно сверять действующий план своей группы.

Содержание

Для названия «Сложность вычислений — 2» первичная программа не найдена. Однако опубликован полный план смежного выборного курса «Сложность вычислений: дополнительные главы», VI семестр, версия от 1 февраля 2024 года. Он не подменяет несуществующую в плане отдельную дисциплину, но полностью раскрыт здесь как доступный материал:

  1. Интерактивные протоколы, классы \(dIP\) и \(IP\), полнота и точность, примеры изоморфизма графов и квадратичных невычетов; включение \(IP\subseteq PSPACE\).
  2. Общая случайность, игры Артура—Мерлина, классы \(AM\) и \(MA\), попарно независимые хеш-функции и протокол Голдвассера—Сипсера.
  3. Теорема Шамира \(IP=PSPACE\): арифметизация, протоколы для \(\#SAT\) и \(TQBF\).
  4. Совершенное, статистическое и вычислительное нулевое разглашение; классы \(PZK\), \(SZK\), \(CZK\) и пример изоморфизма графов.
  5. Односторонние функции, привязка к сообщению, нулевое разглашение для 3-раскраски, идеи включений \(NP\subseteq CZK\) и \(IP\subseteq CZK\).
  6. Вероятностно проверяемые доказательства, класс \(PCP\), приближение NP-полных задач, PCP-теорема и гипотеза Хота.
  7. Протоколы с несколькими пруверами, класс \(MIP\) и равенство \(MIP=MIP2=PCP(poly,poly)=NEXP\).
  8. Рациональные интерактивные доказательства, классы \(FRMA\), \(DRMA\), \(RIP\), иерархия подсчёта.
  9. Сложность тотальных задач поиска: \(TFNP\), классы \(PLS\), \(PPP\), \(PPA\), \(PPAD\) и полные задачи.

В программе также указано, что материалы, задания, частичные решения, индивидуальные домашние задания и тренировочный вариант должны были публиковаться в Telegram-канале и общей папке. В разделе оценивания документа сказано только «будет дополнено»: числовая БРС не опубликована.

Литература в программе 2024

Д. В. Мусатов, Сложность вычислений: классика и современность (черновик); S. Arora, B. Barak, Computational Complexity: A Modern Approach; O. Goldreich, Foundations of Cryptography, Vol. I и Computational Complexity: A Conceptual Perspective; C. Moore, S. Mertens, The Nature of Computation; J. Katz, Notes on Complexity Theory; C. Papadimitriou, Computational Complexity. В качестве сетевых ресурсов названы Complexity Zoo, блог Dick Lipton, Shtetl-Optimized, Computational Complexity Blog и сайты вопросов по теоретической информатике.

Оценивание

Открытая БРС не найдена.

Источники и актуальность

Учебный план 01.03.02, набор 2025 и программа смежного курса, 2024.