Complexity theory 2026

Факультатив представляет собой введение в, пожалуй, центральную подобласть теоретической информатики, а именно в теорию вычислений. Данную науку монжно противопоставить всем известной теории алгоритмов. Цель алгоритмического подхода -- придумать максимально быстрое решение для отдельно взятой задачи. Теория вычислений же исследует общие подходы к построению эффективного решения или, что не менее важно, доказывает его отсутствие. Для данной постановки задачи были введены так называемые сложностные классы, в том числе всем известные P и NP, задача взаимосвязи которых объявлена одной из семи Millennium Prize Problems.

Также курс затронет другие подходы к оценке сложности той или иной задачи, например деревья решений. Также планируется рассказать некоторый обзор результатов из разных предметов, которые будут затрагиваться на специализации "теоретическая информатика": приближенные алгоритмы, экспандеры, конечно, сложность. Этот курс может быть неплохим введением, если вы задумываетесь о поступлении на таковую специалзацию ПМИ.

Каждую неделю будет проходить одна лекция. Также в случайные моменты семестра будут выдаваться задачи для самостоятельного решения.

Общая информация

Официальное название: «Теория вычислений».

Преподаватель: Артём Парфенов, телеграм: @dunno_0

Время и место (с 12 февраля): четверг, 18:10, корпус на Покровском бульваре, аудитория N504. ВРЕМЯ И МЕСТО ПРОВЕДЕНИЯ БУДЕТ УТОЧНЯТЬСЯ НА ПЕРВОМ ЗАНЯТИИ

Телеграм-чат: ссылка.

Таблица с результатами: [ ссылка появится].

История

12 февраля 2026. Занятие 1. Введние. Конечный автомат.. [ Конспект]

Правила оценивания

Оценка складывается из двух пунктов:

Задачи. Решать и сдавать задачи из нижеприведённого списка. Формат сдачи и дедлайны будут оговорены в листке.

Экзамен. Экзамен будет в формате мини-конференции. Каждый студент выбирает статью из нижеприведённого списка и делает по ней доклад.

Итоговая оценка формируется как O_{итоговая} = 0,7 * O_{задачки} + 0,3 * О_экз.

Наборы задач

Интересные статьи

Пока что заранее заготовленные примеры, список будет пополняться (учитывая предпочтения слушающих).

J. Hartmanis & R. E. Stearns. On the complexity of algorithms (1965). (Статья, с которой началась теория сложности вычислений).

Stephen A. Cook. The complexity of theorem-proving procedures (1971). (Определение полноты (осторожно: не совсем такое, как у нас) и теорема Кука-Левина).

Л. А. Левин. Универсальные задачи перебора (1973). (Внушительный список комбинаторных задач с доказательствами их NP-полноты)

M. Agrawal, N. Kayal & N. Saxena. PRIMES is in P (2004). (Полиномиальный алгоритм проверки числа на простоту)

Alexander A. Razborov & Steven Rudich. Natural Proofs

U. Feige & Sh. Jozpeh. Separation between estimation and approximation (Классика приближённых алгоритмов: разделение по сложности задач нахождения оценки и нахождения приближённого решения)

M. Goldmann, J. Hastad & A. Razborov. Majority gates vs. general weighted threshold gates (Фундаментальная, но простая для понимания статья по булевым схемам)

J. Hastad. On the Size of Weights for Threshold Gates (Результат, схожий с предыдущим, только с доказательством конкретной оценки)

R. Moser & G. Tardos. A constructive proof of the general Lovasz Local Lemma (Фундаментальная вещь из вероятностных алгоритмов (которую, кстати, планировал рассказывать Дмитрий Александрович на курсе ТВиМС))

C. Gotsman & N. Linial. The equivalence of two problems on the cube (Один из кусков так называемой "гипотезы о чувствительности", её связь с максимальной степенью подграфа булева куба)

Литература

S. Arora and B. Barak, Computational Complexity: A Modern Approach, 2009 (Более полный учебник конкретно по теории сложности)
Michael Sipser. Introduction to the Theory of Computation (Очень хороший вводный учебник)
Михаил Вялый. Черновик учебника по приближённым алгоритмам.
Ryan O’Donnell. Analysis of boolean functions. (Невероятно качественная книга про булев анализ)