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

Structural Complexity Theory
Saint Petersburg / autumn 2008, посмотреть все семестры

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

Структурная теория сложности изучает классы вычислительных задач и взаимоотношения между ними. Эта область информатики содержит как "великие" нерешенные задачи (например, P vs NP — одна из семи задач, за решение которых Clay Mathematical Institute объявил призы по $1,000,000), так и красивые теоремы (теорема Шамира об интерактивных доказательствах, теорема Разборова о монотонных логических схемах…). Без знания теории сложности невозможно глубокого понимания криптографии и многих других областей теоретической информатики.

Конспекты лекций, читавшихся ранее: http://logic.pdmi.ras.ru/~hirsch/students/complexity1/

Видео лекций https://www.lektorium.tv/course/22750?id=22750

Date and time Class|Name Venue|short Materials
28 September
14:15–15:45
Лекции 1-2, Lecture ПОМИ РАН slides
12 October
14:15–15:45
Лекции 3-4, Lecture ПОМИ РАН slides
26 October
14:15–15:45
Лекции 5-6, Lecture ПОМИ РАН slides
09 November
14:25–15:55
Лекции 7-8, Lecture ПОМИ РАН slides
16 November
14:30–16:00
Лекции 9-10, Lecture ПОМИ РАН slides
23 November
14:30–16:00
Лекции 11-12, Lecture ПОМИ РАН slides