stringtranslate.com

PPAD (сложность)

В информатике PPAD («Polynomial Parity Arguments on Directed graphs») — это класс сложности, введенный Христосом Пападимитриу в 1994 году. PPAD — это подкласс TFNP, основанный на функциях, для которых может быть показано, что они являются тотальными с помощью аргумента четности. [1] [2] Класс привлек значительное внимание в области алгоритмической теории игр , поскольку он содержит задачу вычисления равновесия Нэша : эта задача была показана как полная для PPAD Даскалакисом, Голдбергом и Пападимитриу с по крайней мере 3 игроками, а позже Ченом и Дэном была расширена до 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 .

Дальнейшее чтение

Другие заметные полные проблемы

Ссылки

  1. ^ Христос Пападимитриу (1994). «О сложности аргумента о четности и других неэффективных доказательствах существования» (PDF) . Журнал компьютерных и системных наук . 48 (3): 498–532. doi :10.1016/S0022-0000(05)80063-7. Архивировано из оригинала (PDF) 2016-03-04 . Получено 2008-03-08 .
  2. ^ Фортнау, Лэнс (2005). "Что такое PPAD?" . Получено 29.01.2007 .
  3. ^ ab * Чэнь, Си; Дэн, Сяоте (2006). Урегулирование сложности равновесия Нэша для двух игроков . Труды 47-го симпозиума. Основы компьютерной науки. С. 261–271. doi :10.1109/FOCS.2006.69. ECCC  TR05-140..
  4. ^ Даскалакис, Константинос.; Голдберг, Пол В.; Пападимитриу, Христос Х. (2009-01-01). «Сложность вычисления равновесия Нэша». SIAM Journal on Computing . 39 (1): 195–259. CiteSeerX 10.1.1.152.7003 . doi :10.1137/070699652. ISSN  0097-5397. 
  5. ^ Daskalakis, C.; Papadimitriou, C. (2011-01-23). ​​Непрерывный локальный поиск . Труды. Общество промышленной и прикладной математики. стр. 790–804. CiteSeerX 10.1.1.362.9554 . doi :10.1137/1.9781611973082.62. ISBN  9780898719932. S2CID  2056144.
  6. ^ Скотт Ааронсон (2011). «Почему философы должны заботиться о вычислительной сложности». arXiv : 1108.1791 [cs.CC].
  7. ^ Христос Пападимитриу (2011). «Лекция: Сложность нахождения равновесия Нэша» (PDF) .
  8. ^ ab C. Daskalakis, PW Goldberg и CH Papadimitriou (2009). «Сложность вычисления равновесия Нэша». SIAM Journal on Computing . 39 (3): 195–259. CiteSeerX 10.1.1.152.7003 . doi :10.1137/070699652. 
  9. ^ Фернли, Джон; Голдберг, Пол; Холлендер, Александрос; Савани, Рахул (2022-12-19). «Сложность градиентного спуска: CLS = PPAD ∩ PLS». Журнал ACM . 70 (1): 7:1–7:74. arXiv : 2011.01929 . doi :10.1145/3568163. ISSN  0004-5411. S2CID  263706261.
  10. ^ Яннакакис, Михалис (2009-05-01). «Равновесия, неподвижные точки и классы сложности». Computer Science Review . 3 (2): 71–85. arXiv : 0802.2831 . doi :10.1016/j.cosrev.2009.03.004. ISSN  1574-0137.
  11. ^ Си Чэнь и Сяоте Дэн (2006). «О сложности двумерной дискретной задачи с фиксированной точкой». Международный коллоквиум по автоматам, языкам и программированию . С. 489–500. ECCC  TR06-037.
  12. ^ Дэн, X.; Ци, Q.; Сабери, A. (2012). «Алгоритмические решения для разрезания торта без зависти». Исследование операций . 60 (6): 1461. doi :10.1287/opre.1120.1116. S2CID  4430655.