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

Computational complexity of search problems
Saint-Petersburg / autumn 2018, посмотреть все семестры

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

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

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

Date and time Class|Name Venue|short Materials
22 September
17:15–18:45
Лекция 1, lecture ПОМИ РАН slidesvideo
22 September
19:00–20:30
Лекция 2, lecture ПОМИ РАН video
23 September
11:15–12:45
Лекция 3, lecture ПОМИ РАН video
23 September
13:00–14:30
Лекция 4, lecture ПОМИ РАН video