Основы вычислимости и теории сложности

Санкт-Петербург, осень 2012

Описание

Курс дает ответы на такие вопросы: Что такое алгоритм? Что такое эффективный алгоритм? Что такое доказательство? Как доказать, что нет алгоритма, который решит данную задачу? Как доказать, что что-то нельзя доказать? Как понять, что нет эффективного алгоритма для данной задачи? Что такое сложность объекта? Из курса можно узнать, что такое вычислимые функции, арифметическая иерархия, колмогоровская сложность, классы P, NP, PSPACE и пр., полиномиальная иерархия, схемная сложность, сложность с ограничением по памяти и многие другие интересные вещи.

Преподаватели

Список лекций

Разрешимые и перечислимые множества. Классы P и NP

Разрешимые множества, определения перечислимого множества. Теорема Поста. Классы P и NP. m-сведение, самое трудное перечислимое множество. Неразрешимость задачи об остановке алгоритма.

Разрешимые и перечислимые множества. Классы P и NP

Разрешимые множества, определения перечислимого множества. Теорема Поста. Классы P и NP. m-сведение, самое трудное перечислимое множество. Неразрешимость задачи об остановке алгоритма.

Вычислимые функции

Неразрешимость разных задач, сведение по Карпу, NP-полнота задачи об ограниченной остановке. Вычислимые функции, вычислимость функции и перечислимость ее графика, пример числа, которое является пределом вычислимой последовательности, но не приближается алгоритмически, диагональная функция и то, что ее нельзя продолжить до всюду определенной, главные нумерации вычислимых функций. Теорема Успенского-Райса. другие примеры неразрешимых множеств. Последовательность Шпеккера. Теорема Успенского-Райса.

Вычислимые функции

Неразрешимость разных задач, сведение по Карпу, NP-полнота задачи об ограниченной остановке. Вычислимые функции, вычислимость функции и перечислимость ее графика, пример числа, которое является пределом вычислимой последовательности, но не приближается алгоритмически, диагональная функция и то, что ее нельзя продолжить до всюду определенной, главные нумерации вычислимых функций. Теорема Успенского-Райса. другие примеры неразрешимых множеств. Последовательность Шпеккера. Теорема Успенского-Райса.

Теорема о неподвижной точке. Машины Тьюринга

Теорема о неподвижной точке. Программа, печатающая свой текст. Доказательство с помощью искусственного языка программирования. Машины Тьюринга. Неразрешимость задачи Поста.

Теорема о неподвижной точке. Машины Тьюринга

Теорема о неподвижной точке. Программа, печатающая свой текст. Доказательство с помощью искусственного языка программирования. Машины Тьюринга. Неразрешимость задачи Поста.

Вычислимость и выразимость в арифметике

Формулы исчисления предикатов. Выразимость в арифметике. Арифметичность перечислимых множеств.

Вычислимость и выразимость в арифметике

Формулы исчисления предикатов. Выразимость в арифметике. Арифметичность перечислимых множеств.

Арифметическая иерархия. Колмогоровская сложность

Арифметическая иерархия и ее простейшие свойства. Универсальные множества в арифметической иерархии. Строгость арифметической иерархии. Теоремы Тарского и Геделя. Системы доказательств и перечислимые множества. Колмогоровская сложность, ее невычислимость. Доказательство Чайтина теоремы Геделя о неполноте.

Арифметическая иерархия. Колмогоровская сложность

Арифметическая иерархия и ее простейшие свойства. Универсальные множества в арифметической иерархии. Строгость арифметической иерархии. Теоремы Тарского и Геделя. Системы доказательств и перечислимые множества. Колмогоровская сложность, ее невычислимость. Доказательство Чайтина теоремы Геделя о неполноте.

Моделирование машин Тьюринга. Недетерминированные машины Тьюринга

Нижняя оценка на палиндром на одноленточной машине Тьюринга. Моделирование k-ленточной машины на k-ленточной с линейным замедлением. Эффективное моделирование k-ленточной машины на 2-ленточной. Недетерминированные машины Тьюринга и класс NP. Задача Circuit-SAT, сведение Circuit-SAT к 3SAT.

Моделирование машин Тьюринга. Недетерминированные машины Тьюринга

Нижняя оценка на палиндром на одноленточной машине Тьюринга. Моделирование k-ленточной машины на k-ленточной с линейным замедлением. Эффективное моделирование k-ленточной машины на 2-ленточной. Недетерминированные машины Тьюринга и класс NP. Задача Circuit-SAT, сведение Circuit-SAT к 3SAT.

О классе NP

NP-полнота задачи Circuit-SAT и задачи о независимом множестве. NP-задачи поиска. Сведения по Тьюрингу. Сведение задач поиска к задачам распознавания. Теорема Ладнера.

О классе NP

NP-полнота задачи Circuit-SAT и задачи о независимом множестве. NP-задачи поиска. Сведения по Тьюрингу. Сведение задач поиска к задачам распознавания. Теорема Ладнера.

P vs NP с оракулами. Иерархии по времени

Оракулы при которых P=NP и PNP. Иерархия по времени для детерминированных и недетерминированных вычислений.

P vs NP с оракулами. Иерархии по времени

Оракулы при которых \(P=NP\) и \(P\neq NP\). Иерархия по времени для детерминированных и недетерминированных вычислений.

Вычисления с ограничениями по памяти

Теорма Савича и следствие о NPSPACE = PSPACE. Полнота TQBF в классе PSPACE. Теорема об иерархии по памяти. Логарифмические по памяти сведения и их свойства. Класс NL, полная задача в нем.

Вычисления с ограничениями по памяти

Теорма Савича и следствие о NPSPACE = PSPACE. Полнота TQBF в классе PSPACE. Теорема об иерархии по памяти. Логарифмические по памяти сведения и их свойства. Класс NL, полная задача в нем.

Полиномиальная иерархия

Замкнутость классов NSpace[s(n)] относительно дополнения. Полиномиальная иерархия. Простейшие свойства, полные задачи в \Sigma_i^P и в \Pi_i^P. Оракульное определение полиномиальной иерархии.

Полиномиальная иерархия

Замкнутость классов NSpace[s(n)] относительно дополнения. Полиномиальная иерархия. Простейшие свойства, полные задачи в \(\Sigma_i^P\) и в \(\Pi_i^P\). Оракульное определение полиномиальной иерархии.

Нижние оценки для SAT. Схемная сложность

Вычисления с ограничением по времени и по памяти. Нижняя оценка для SAT. Альтернирующие машины Тьюринга и полиномиальная иерархия. Булевы схемы. Вычисления с подсказкой. Класс P/poly. Включение P в P/poly. Теорема Карпа-Липтона. Существование функций большой схемной сложности.

Нижние оценки для SAT. Схемная сложность

Вычисления с ограничением по времени и по памяти. Нижняя оценка для SAT. Альтернирующие машины Тьюринга и полиномиальная иерархия. Булевы схемы. Вычисления с подсказкой. Класс P/poly. Включение P в P/poly. Теорема Карпа-Липтона. Существование функций большой схемной сложности.

Схемы и параллельные вычисления

Языки большой схемной сложности в полиномиальной иерархии (теорема Каннана). Равномерные схемы. Классы NC и NC. P-полные задачи. Соотношение между NC, L, NL и NC. Замкнутость NC относительно логарифмических по памяти сведений. Эффективные параллельные схемы для сложения и умножения чисел.

Схемы и параллельные вычисления

Языки большой схемной сложности в полиномиальной иерархии (теорема Каннана). Равномерные схемы. Классы \(NC\) и \(NC^i\). P-полные задачи. Соотношение между \(NC^1\), \(L\), \(NL\) и \(NC^2\). Замкнутость NC относительно логарифмических по памяти сведений. Эффективные параллельные схемы для сложения и умножения чисел.