В информатике , PPAD ( «полиномиальные Паритеты Аргументы на графах Directed») является класс сложности введена Пападимитим в 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 with 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 принадлежит к тому же классу, что и FP , и все еще имеет P NP , хотя это кажется маловероятным. [ необходимая цитата ] Примеры PPAD-полных задач включают нахождение равновесий по Нэшу , вычисление фиксированных точек в функциях Брауэра и нахождение равновесий Эрроу-Дебре на рынках. [8]
Другие заметные полные проблемы
- Нахождение равновесия по Нэшу в игре с двумя игроками [3] или эпсилон-равновесия в игре с любым количеством игроков. [8]
- Нахождение трехцветной точки в лемме Спернера . [9]
- Найти пирожное без зависти, когда функции полезности задаются алгоритмами с полиномиальным временем. [10]
Рекомендации
- ↑ Христос Пападимитриу (1994). «О сложности аргумента четности и других неэффективных доказательствах существования» (PDF) . Журнал компьютерных и системных наук . 48 (3): 498–532. DOI : 10.1016 / S0022-0000 (05) 80063-7 . Архивировано из оригинального (PDF) 04 марта 2016 года . Проверено 8 марта 2008 .
- ^ Фортноу, Лэнс (2005). "Что такое PPAD?" . Проверено 29 января 2007 .
- ^ а б * Чен, Си; Дэн, Сяотэ (2006). Урегулирование сложности равновесия по Нэшу для двух игроков . Proc. 47-й симпозиум. Основы компьютерных наук. С. 261–271. DOI : 10.1109 / FOCS.2006.69 . ECCC TR05-140 ..
- ^ Даскалакис, Константинос .; Голдберг, Пол В .; Пападимитриу, Христос Х. (1 января 2009 г.). «Сложность вычисления равновесия по Нэшу» . SIAM Journal on Computing . 39 (1): 195–259. DOI : 10.1137 / 070699652 . ISSN 0097-5397 .
- ^ Daskalakis, C .; Пападимитриу, К. (23 января 2011 г.). Непрерывный локальный поиск . Ход работы. Общество промышленной и прикладной математики. С. 790–804. CiteSeerX 10.1.1.362.9554 . DOI : 10.1137 / 1.9781611973082.62 . ISBN 9780898719932.
- ^ Скотт Ааронсон (2011). «Почему философы должны заботиться о вычислительной сложности». arXiv : 1108.1791 [ cs.CC ].
- ^ Христос Пападимитриу (2011). "Лекция: Сложность поиска равновесия по Нэшу" (PDF) .
- ^ а б К. Даскалакис, П. У. Голдберг и С. К. Пападимитриу (2009). «Сложность вычисления равновесия по Нэшу». SIAM Journal on Computing . 39 (3): 195–259. CiteSeerX 10.1.1.152.7003 . DOI : 10.1137 / 070699652 .
- ^ Си Чен и Сяотэ Дэн (2006). «О сложности двумерной дискретной задачи о неподвижной точке». Международный коллоквиум по автоматам, языкам и программированию . С. 489–500. ECCC TR06-037 .
- ^ Дэн, X .; Ци, Q .; Сабери, А. (2012). «Алгоритмические решения для вырезания торта без зависти». Исследование операций . 60 (6): 1461. DOI : 10,1287 / opre.1120.1116 .