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 .

• Равновесия, неподвижные точки и классы сложности: обзор. ^[10]

• Нахождение равновесия Нэша в игре с двумя игроками ^[3] или Эпсилон-равновесия в игре с любым количеством игроков. ^[8]

• Нахождение трехцветной точки в лемме Шпернера . ^[11]
• Нахождение разрезания торта без зависти , когда функции полезности задаются алгоритмами с полиномиальным временем. ^[12]