RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Межкафедральный семинар МФТИ по дискретной математике
26 октября 2016 г. 18:30, г. Долгопрудный, Актовый зал Лабораторного корпуса МФТИ
 


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

Д. В. Мусатов

Количество просмотров:
Эта страница:108

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

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020