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

В Информатика, PPAD («Аргументы полиномиальной четности на ориентированных графах») является класс сложности представлен Христос Пападимитриу в 1994 году. PPAD является подклассом TFNP на основе функций, которые можно показать как итоговые с помощью аргумента четности.[1][2] Класс привлек значительное внимание в области алгоритмическая теория игр потому что он содержит проблему вычисления равновесие по Нэшу: Даскалакис, Голдберг и Пападимитриу показали, что эта задача для PPAD завершена для PPAD как минимум с 3 игроками, а позже Чен и Дэн расширили ее до 2 игроков.[3][4]

Определение

PPAD - это подмножество класса TFNP, класс функциональные проблемы в ФНП которые гарантированно будут общий. В TFNP формальное определение дается следующим образом:

Бинарное отношение P (Икс,у) находится в TFNP тогда и только тогда, когда существует детерминированный алгоритм полиномиального времени, который может определить, является ли P (Икс,у) выполняется при обоих Икс и у, и для каждого Икс, существует у такое, что P (Икс,у) имеет место.

Подклассы TFNP определяются на основе типа математического доказательства, используемого для доказательства того, что решение всегда существует. Неформально PPAD - это подкласс TFNP, где гарантия того, что существует у такое, что P (Икс,у) выполняется на основе аргумента четности на ориентированном графе. Класс формально определяется путем определения одной из полных проблем, известных как Конец строки:

G - ориентированный граф (возможно, экспоненциально большой) без изолированных вершин и с каждым вершина иметь не более одного предшественника и одного преемника. G задается путем задания вычислимой за полиномиальное время функции f (v) (многочлен размером v), который возвращает предшественника и преемника (если они существуют) вершины v. Учитывая вершину s в G без предшественника найти вершину т ≠ с без предшественника или без преемника. (Входом в задачу является исходная вершина s а функция f (v)). Другими словами, нам нужен любой источник или сток ориентированного графа, кроме s.

Такой т должен существовать, если s делает, потому что структура G означает, что вершины только с одним соседом входят парами. В частности, учитывая s, мы можем найти такой т на другом конце строки, начиная с 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-complete включают поиск Равновесия Нэша, вычисляя неподвижные точки в Брауэр функции, поиск Равновесия Эрроу-Дебре на рынках.[8]

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

Основная статья: Список проблем PPAD-complete

Рекомендации

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