PPA (сложность) - PPA (complexity)
В теории сложности вычислений , PPA является классом сложности , стоящий за «полиномиальный Паритет аргумент» (на графике). Представленный Христосом Пападимитриу в 1994 году (стр. 528), PPA является подклассом TFNP . Это класс задач поиска, который можно показать как тотальный, применяя лемму о подтверждении связи : любой неориентированный граф, имеющий вершину, степень которой нечетное число, должен иметь некоторую другую вершину, степень которой является нечетным числом . Это наблюдение означает, что если нам дан граф и вершина нечетной степени, и нас просят найти какую-то другую вершину нечетной степени, то мы ищем то, что гарантированно существует (так что у нас есть проблема полного поиска ).
PPA определяется следующим образом. Предположим, у нас есть граф, вершины которого представляют собой -битовые двоичные строки, и граф представлен схемой полиномиального размера, которая принимает вершину в качестве входных данных и выводит ее соседей. (Обратите внимание, что это позволяет нам представить экспоненциально большой граф, на котором мы можем эффективно выполнять локальное исследование.) Предположим, кроме того, что конкретная вершина (скажем, вектор со всеми нулями) имеет нечетное количество соседей. Требуется найти еще одну вершину нечетной степени. Обратите внимание на то, что эта проблема находится в NP - данное решение может быть проверено с помощью схемы, что решение является правильным. Задача вычисления функции принадлежит PPA, если она допускает полиномиальное сокращение этой задачи поиска графа. Проблема считается полной для класса PPA, если, кроме того, эта задача поиска по графу сводится к этой задаче.
PPA содержит PPAD как подкласс. Это связано с тем, что соответствующая проблема, которая определяет PPAD, известная как КОНЕЦ ЛИНИИ, может быть сведена (прямым способом) к вышеупомянутому поиску дополнительной вершины нечетной степени (по сути, просто игнорируя направления ребер в END ЛИНИИ).
Известно, что неориентированная версия леммы Спернера является полной для PPA. Как известно, проблема консенсуса вдвое, которая является вычислительной версией теоремы Хобби – Райса , является полной для PPA. Проблема поиска второго гамильтонова цикла на 3-регулярном графе является членом PPA, но, как известно, не является полной для PPA. Существует рандомизированное сокращение за полиномиальное время от задачи целочисленной факторизации до задач, полных для PPA.