City: Saint-Petersburg Kazan Language: Русский English

PCP-theorem and approximation algorithms
Kazan / spring 2015, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

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

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

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

Date and time Class|Name Venue|short Materials
04 April
11:50–13:20
Лекция 1, lecture 2-й учебный корпус К(П)ФУ No
04 April
13:35–15:05
Лекция 2, lecture 2-й учебный корпус К(П)ФУ No
05 April
11:50–13:20
Лекция 3, lecture 2-й учебный корпус К(П)ФУ No
05 April
13:35–15:05
Лекция 4, lecture 2-й учебный корпус К(П)ФУ No
06 April
08:30–10:00
Лекция 5, lecture 2-й учебный корпус К(П)ФУ No
06 April
10:10–11:40
Лекция 6, lecture 2-й учебный корпус К(П)ФУ No