Город: Санкт-Петербург Казань Язык: Русский English

Вычислительная сложность задач поиска
Санкт-Петербург / осень 2018, посмотреть все семестры

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

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

С точки зрения сложности вычислений подобные задачи образуют класс TFNP (total functional NP). Более точно, задача состоит в том, чтобы по данному x найти y, такой что выполнено V(x,y). При этом V вычисляется за полиномиальное время, и хотя бы один y существует для любого x (это свойство называется тотальностью). По всей видимости, в этом классе нет полных задач: непонятно, как в общем случае проверять тотальность. Основной метод анализа состоит в том, чтобы выделять те или иные математические принципы, из которых следует тотальность, и рассматривать классы задач, основанных на одном принципе. Наиболее известны классы PLS, PPA, PPAD и PPP, введённые Христосом Пападимитриу. Оказалось, что задачи, связанные с экономическими равновесиями, попадают в класс PPAD, и многие из них полны в нём. В курсе будет дан обзор современного состояния этой области: на первых двух лекциях излагается классическая теория, на вторых двух - достижения последних лет.

Дата и время Название Место Материалы
22 сентября
17:15–18:45
Лекция 1, лекция ПОМИ РАН слайдывидео
22 сентября
19:00–20:30
Лекция 2, лекция ПОМИ РАН видео
23 сентября
11:15–12:45
Лекция 3, лекция ПОМИ РАН видео
23 сентября
13:00–14:30
Лекция 4, лекция ПОМИ РАН видео