Вычислительная сложность задач поиска

Санкт-Петербург, осень 2018

Описание

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

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

Преподаватели

Список лекций

Лекция 1

Задачи поиска и распознавания. Их эквивалентность для NP-полных задач и изоморфизма графов. Класс TFNP и его подклассы. Классификация различных задач.

Лекция 2

Полные задачи в классе PPAD: конструктивные аналоги леммы Шпернера, теорем Брауэра и Какутани, равновесие Нэша и экономические равновесия.

Лекция 3

Сильная и слабая аппроксимация в теоремах о неподвижных точках. Теория Этессами-Яннакакиса о сложности сильной аппроксимации: класс FIXP и его сложностной статус. Теорема Рубинштейна о PPAD-полноте задачи о слабой аппроксимации с константной степенью приближения.

Лекция 4

Теория Голдберга-Пападимитриу: в поисках общего подхода к TFNP. Класс PTFNP доказуемо тотальных задач и полнота в нём задачи о поиске ошибки в доказательстве 2x2=5. Связь с другими известными классами.