Сложностные классы задач поиска. Часть 2

Вычислительная задача поиска ставится так: требуется либо найти объект с некоторым свойством, либо указать, что его не существует. В соответствующей задаче распознавания находить объект не требуется, нужно лишь понять, существует он или нет. Ясно, что задача распознавания не сложнее задачи поиска, но иногда может быть проще. Так, для задачи разложения на множителя сложности скорее всего различаются: проверить, что число составное, можно за полиномиальное время AKS-алгоритмом, а найти разложение скорее всего нельзя. А вот для NP-полных задач сложности одинаковы. Отдельный интерес представляют тотальные задачи поиска, в которых объект точно существует и потому задача распознавания тривиальна. Оказывается, они разбиваются на классы в зависимости от того, какой именно аргумент используется для доказательства существования. Где-то это принцип Дирихле (класс PPP), где-то — теорема о том, что число вершин нечётной степени в любом графе чётно (класс PPA), где-то — частный случай этой теоремы для графов со степенями вершин не больше 2 (класс PPAD). Особенно интересен класс PPAD: в него попадают конструктивные версии задач, связанных с неподвижными точками и математической экономикой. Например, это поиск пёстрого симплекса в лемме Шпернера, неподвижной точки в теореме Брауэра, равновесия Нэша в матричных играх, равновесия Вальраса в экономике обмена и т.д. Более того, все эти задачи полны в классе PPAD, т.е. к ним сводится любая другая задача из этого класса. В докладе будет сделан обзор классов задач поиска, определён ряд PPAD-полных задач и продемонстрированы основные идеи доказательства их полноты.