ППАД (сложность)
В информатике , PPAD («Аргументы полиномиальной четности на ориентированных графах») — это класс сложности введенный Кристосом Пападимитриу в 1994 году. PPAD — это подкласс TFNP, основанный на функциях, сумма которых может быть показана с помощью аргумента четности. [1] [2] Этот класс привлек значительное внимание в области алгоритмической теории игр , поскольку он содержит задачу вычисления равновесия по Нэшу : Даскалакис, Голдберг и Пападимитриу показали, что эта задача является полной для PPAD с по крайней мере тремя игроками, а затем была расширена Ченом и Дэном. для 2 игроков. [3] [4]
Определение
[ редактировать ]PPAD является подмножеством класса TFNP , класса функциональных задач в FNP, которые гарантированно являются тотальными . Формальное определение TFNP : дается следующим образом
- Бинарное отношение P( x , y ) находится в TFNP тогда и только тогда, когда существует детерминированный алгоритм с полиномиальным временем, который может определить, выполняется ли P( x , y ) при заданных как x, так и y , и для каждого x существует y , такой что P( x , y ) выполняется.
Подклассы TFNP определяются на основе типа математического доказательства, используемого для доказательства того, что решение всегда существует. Неформально PPAD — это подкласс TFNP, где гарантия существования y такого, что P( x , y ) выполняется, основана на аргументе четности в ориентированном графе. Класс формально определяется путем указания одной из его полных задач, известной как End-Of-The-Line :
- G — ориентированный граф (возможно, экспоненциально большой), каждая вершина которого имеет не более одного предшественника и не более одного преемника. G задается путем предоставления вычислимой за полиномиальное время функции f( v ) (полиномиальной по размеру v ), которая возвращает предшественника и преемника (если они существуют) вершины v . Учитывая вершину s в G, не имеющую предшественника, найдите вершину t≠s без предшественника или преемника. (Входными данными для задачи являются исходная вершина s и функция f( v )). Другими словами, нам нужен любой источник или приемник ориентированного графа, отличный от s .
Такой t должен существовать, если существует s , потому что структура G означает, что вершины только с одним соседом располагаются парами. В частности, учитывая s , мы можем найти такую t на другом конце строки, начиная с s . (Обратите внимание, что это может занять экспоненциальное время, если мы будем просто многократно вычислять f.)
Отношения с другими классами сложности
[ редактировать ]PPAD содержится (но не известно, что он равен) PPA (соответствующий класс аргументов четности для неориентированных графов), который содержится в TFNP. (но не равен ему) PPAD также содержится в PPP , другом подклассе TFNP. Он содержит CLS . [5]
PPAD — это класс задач, которые считаются сложными, но получение PPAD-полноты является более слабым свидетельством неразрешимости, чем достижение NP-полноты . Проблемы PPAD не могут быть NP-полными по той технической причине, что NP представляет собой класс задач решения, но ответ на задачи PPAD всегда положительный, поскольку известно, что решение существует, даже если найти это решение может быть трудно. [6] Однако PPAD и NP тесно связаны. Хотя вопрос, существует ли равновесие Нэша для данной игры, не может быть NP-сложным, поскольку ответ всегда положительный, вопрос о существовании второго равновесия является NP-полным. [7] Примеры PPAD-полных задач включают поиск равновесия Нэша , вычисление фиксированных точек в функциях Брауэра и поиск равновесия Эрроу-Дебре на рынках. [8]
Фернли, Голдберг, Холлендер и Савани [9] доказал, что класс сложности под названием CLS равен пересечению PPAD и PLS .
Дальнейшее чтение
[ редактировать ]- Равновесия, фиксированные точки и классы сложности: обзор. [10]
Другие заметные полные проблемы
[ редактировать ]- Нахождение равновесия Нэша в игре для двух игроков. [3] или Эпсилон-равновесие в игре с любым количеством игроков. [8]
- Нахождение трехцветной точки в лемме Спернера . [11]
- Найти разрез торта без зависти , когда функции полезности задаются алгоритмами с полиномиальным временем. [12]
Ссылки
[ редактировать ]- ^ Христос Пападимитриу (1994). «О сложности аргумента четности и других неэффективных доказательствах существования» (PDF) . Журнал компьютерных и системных наук . 48 (3): 498–532. дои : 10.1016/S0022-0000(05)80063-7 . Архивировано из оригинала (PDF) 4 марта 2016 г. Проверено 8 марта 2008 г.
- ^ Фортнау, Лэнс (2005). «Что такое ППАД?» . Проверено 29 января 2007 г.
- ^ Jump up to: а б * Чен, Си; Дэн, Сяоте (2006). Урегулирование сложности равновесия Нэша для двух игроков . Учеб. 47-й симп. Основы информатики. стр. 261–271. дои : 10.1109/FOCS.2006.69 . ЕССС ТР05-140 . .
- ^ Даскалакис, Константинос.; Голдберг, Пол В.; Пападимитриу, Христос Х. (1 января 2009 г.). «Сложность вычисления равновесия Нэша» . SIAM Journal по вычислительной технике . 39 (1): 195–259. CiteSeerX 10.1.1.152.7003 . дои : 10.1137/070699652 . ISSN 0097-5397 .
- ^ Даскалакис, К.; Пападимитриу, К. (23 января 2011 г.). Непрерывный локальный поиск . Слушания. Общество промышленной и прикладной математики. стр. 790–804. CiteSeerX 10.1.1.362.9554 . дои : 10.1137/1.9781611973082.62 . ISBN 9780898719932 . S2CID 2056144 .
- ^ Скотт Ааронсон (2011). «Почему философы должны заботиться о сложности вычислений». arXiv : 1108.1791 [ cs.CC ].
- ^ Христос Пападимитриу (2011). «Лекция: Сложность поиска равновесия Нэша» (PDF) .
- ^ Jump up to: а б К. Даскалакис, П.В. Голдберг и Ч. Пападимитриу (2009). «Сложность расчета равновесия Нэша». SIAM Journal по вычислительной технике . 39 (3): 195–259. CiteSeerX 10.1.1.152.7003 . дои : 10.1137/070699652 .
- ^ Фернли, Джон; Гольдберг, Пол; Холлендер, Александрос; Савани, Рахул (19 декабря 2022 г.). «Сложность градиентного спуска: CLS = PPAD ∩ PLS» . Журнал АКМ . 70 (1): 7:1–7:74. arXiv : 2011.01929 . дои : 10.1145/3568163 . ISSN 0004-5411 . S2CID 263706261 .
- ^ Яннакакис, Михалис (1 мая 2009 г.). «Равновесия, неподвижные точки и классы сложности» . Обзор компьютерных наук . 3 (2): 71–85. arXiv : 0802.2831 . дои : 10.1016/j.cosrev.2009.03.004 . ISSN 1574-0137 .
- ^ Си Чен и Сяоте Дэн (2006). «О сложности двумерной дискретной задачи с фиксированной точкой». Международный коллоквиум по автоматам, языкам и программированию . стр. 489–500. ЕССС ТР06-037 .
- ^ Дэн, X.; Ци, К.; Сабери, А. (2012). «Алгоритмические решения для разрезания тортов без зависти». Исследование операций . 60 (6): 1461. doi : 10.1287/opre.1120.1116 . S2CID 4430655 .