Классификация задач по сложности алгоритмического решения. Разрешимые и полуразрешимые (перечислимые) множества.

Доказательства и перечислимость. Неразрешимость проблемы остановки.

Почему не все истины можно доказать (Гёдель). Сведение как метод доказательства неразрешимости.

Игра Конвея.

Полиномиально разрешимые задачи, хорошие и плохие вычислительные модели.

Схемная сложность. Полиномиальные задачи имеют полиномиальные схемы.

Неконструктивное доказательство существования сложных задач. Задачи из класса NP: примеры. Полиномиальные сведения задач: примеры. CIRCUIT-SAT к 3SAT. Полнота задачи 3SAT.

Двойственность: препятствие к существованию решения в виде конкретного объекта, на примере Форда-Фалкерсона.

Исчисление резолюций и его полнота.

Линейное программирование: у неразрешимой системы линейных неравенств есть препятствие в виде линейной комбинации этих неравенств, дающей противоречие.

Конечная игра с полной информацией: препятствие к выигрышной стратегии одного игрока - выигрышная стратегия второго.

Полиномиальные игры и их решение в классе PSPACE.

Пример полной полиномиальной игры.

Вероятностные алгоритмы. Что такое вероятностное пространство и где оно в этих алгоритмах.

Почему для абстрактной вычислимости вероятностные алгоритмы не помогают. Порядковая статистика и среднее линейное время.

Быстрая сортировка и среднее логарифмическое время.

Коммуникационная сложность и проверка равенства с логарифмической сложностью и с \(O(1)\) сложностью с публичными битами. Проверка полиномиальных тождеств в случайной точке. one-time pad и надёжность (неотличимость).

Amplification, \(BPP \subset P_{/poly}\).

Конечные автоматы и теорема Клини.

Коды: граница Хемминга и Варшамова-Гилберта.

Код Рида-Соломона. Беспрефиксные коды, лемма Крафта, энтропия.

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

Неизоморфизм графов.

Zero-knowledge proofs.

Изоморфизм графов.

Псевдослучайные генераторы: определение.

Как из одного бита сделать несколько: hybrid argument.

Ценность сложных задач: разложение на простые как модель digital cash.

Колмогоровская сложность, отсутствие вычислимых нижних оценок, парадокс Ришара.