Сайт в процессе наполнения. Архив всех прошедших курсов доступен на старой версии сайта по адресу old.compsciclub.ru
Город: Санкт-Петербург Казань Язык: Русский English

PCP-теорема и приближённое решение NP-трудных задач
Весна 2015, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

PCP - это область, в которой вещи, абсолютно не связанные друг с другом на первый взгляд, оказываются лишь переформулировкой друг друга.

Первый сюжет таков. Многие задачи оптимизации являются NP-трудными. Однако точное значение оптимума часто не нужно, достаточно найти его приближенно. Если это можно сделать за полиномиальное время, то задачу можно считать легкорешаемой. Оказывается, для многих (но не всех!) задач даже приближенное решение с достаточной точностью будет NP-трудным.

Второй сюжет. Чтобы проверить обычное математическое доказательство, нужно прочесть его целиком. Ошибка лишь в одном переходе перечеркивает всё доказательство. Вероятностно проверяемое доказательство - такая форма записи доказательства, в которой достаточно проверить ограниченное число случайно выбранных битов, чтобы с высокой вероятностью найти ошибку. Оказывается, для любого NP-языка можно предъявить такую систему доказательств принадлежности к нему.

На первый взгляд эти два сюжета абсолютно не связаны, но на самом деле между ними можно установить эквивалентность. В мини-курсе мы подробно изучим эту эквивалентность, наметим схему доказательства знаменитой PCP-теоремы о существовании вероятностно проверяемых доказательств для всех языков из NP, а также познакомимся со сложностью приближения некоторых конкретных задач.

Дата и время Название Место Материалы
04 апреля
11:50–13:20
Лекция 1, лекция 2-й учебный корпус К(П)ФУ Нет
04 апреля
13:35–15:05
Лекция 2, лекция 2-й учебный корпус К(П)ФУ Нет
05 апреля
11:50–13:20
Лекция 3, лекция 2-й учебный корпус К(П)ФУ Нет
05 апреля
13:35–15:05
Лекция 4, лекция 2-й учебный корпус К(П)ФУ Нет
06 апреля
08:30–10:00
Лекция 5, лекция 2-й учебный корпус К(П)ФУ Нет
06 апреля
10:10–11:40
Лекция 6, лекция 2-й учебный корпус К(П)ФУ Нет