PPAD (сложность) - PPAD (complexity)
В информатике , PPAD ( «полиномиальные Паритеты Аргументы на графах Directed») является класс сложности введена Пападимитим в 1994 году PPAD подкласс TFNP на основе функций , которые могут быть показанными быть тотальным на аргументе четности. Этот класс привлек значительное внимание в области алгоритмической теории игр, поскольку он содержит проблему вычисления равновесия по Нэшу : эта задача была показана как полная для PPAD Даскалакисом, Голдбергом и Пападимитриу с минимум 3 игроками, а затем расширена Ченом и Дэн. до 2 игроков.
Определение
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 .
PPAD - это класс проблем, которые считаются сложными, но получение полноты PPAD является более слабым свидетельством неразрешимости, чем получение NP-полноты . Проблемы PPAD не могут быть NP-полными по той технической причине, что NP - это класс проблем принятия решений, но ответ проблем PPAD всегда - да, поскольку решение существует, даже если это решение может быть трудным. Однако PPAD и NP тесно связаны. Хотя вопрос о том, существует ли равновесие по Нэшу для данной игры, не может быть NP-трудным, потому что ответ всегда положительный, вопрос о существовании второго равновесия является NP полным. Возможно, PPAD принадлежит к тому же классу, что и FP , и все еще имеет P ≠ NP , хотя это кажется маловероятным. Примеры PPAD-полных задач включают поиск равновесий по Нэшу , вычисление фиксированных точек в функциях Брауэра и нахождение равновесий Эрроу-Дебре на рынках.
Другие заметные полные проблемы
- Нахождение равновесия по Нэшу в игре с двумя игроками или эпсилон-равновесия в игре с любым количеством игроков.
- Нахождение трехцветной точки в лемме Спернера .
- Найти пирожное без зависти, когда функции полезности задаются алгоритмами с полиномиальным временем.