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

В теория сложности вычислений, PPA это класс сложности, что означает «аргумент полиномиальной четности» (на графике). Представлен Христос Пападимитриу в 1994[1] (стр. 528), PPA является подклассом TFNP. Это класс задач поиска, которые можно показать как совокупность путем применения лемма о рукопожатии: любой неориентированный граф, имеющий вершину, степень которой нечетное число, должен иметь некоторую другую вершину, степень которой является нечетным числом. Это наблюдение означает, что если нам дан граф и вершина нечетной степени, и нас попросят найти какую-то другую вершину нечетной степени, то мы ищем то, что гарантированно существует (так что у нас есть проблема полного поиска ).

PPA определяется следующим образом. Предположим, у нас есть граф, вершинами которого являются -битовые двоичные строки, а граф представлен схемой полиномиального размера, которая принимает вершину в качестве входных данных и выводит ее соседей. (Обратите внимание, что это позволяет нам представить экспоненциально большой граф, на котором мы можем эффективно выполнять локальное исследование.) Предположим, кроме того, что конкретная вершина (скажем, вектор со всеми нулями) имеет нечетное количество соседей. Требуется найти еще одну вершину нечетной степени. Обратите внимание, что эта проблема находится в NP - данное решение может быть проверено с помощью схемы, что решение является правильным. Задача вычисления функции относится к PPA, если она допускает редукция за полиномиальное время к этой задаче поиска графа. Проблема в том полный для класса PPA, если вдобавок эта задача поиска графа сводится к этой задаче.

PPA содержит PPAD как подкласс. Это связано с тем, что соответствующая проблема, которая определяет PPAD, известная как КОНЕЦ ЛИНИИ, может быть сведена (прямым способом) к вышеупомянутому поиску дополнительной вершины нечетной степени (по сути, просто игнорируя направления ребер в END ЛИНИИ).

Известно, что неориентированная версия леммы Спернера является полной для PPA.[2] Проблема сокращения вдвое консенсуса, которая представляет собой вычислительную версию Теорема Хобби-Райса, как известно, является полным для PPA.[3] Проблема поиска секунды Гамильтонов цикл на 3-регулярном графе является членом PPA, но, как известно, не является полным для PPA. Существует рандомизированная редукция за полиномиальное время из проблемы Целочисленная факторизация к задачам, завершенным для PPA[4].

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

  1. ^ Христос Пападимитриу (1994). «О сложности аргумента о четности и других неэффективных доказательствах существования» (PDF). Журнал компьютерных и системных наук. 48 (3): 498–532. Дои:10.1016 / S0022-0000 (05) 80063-7. Архивировано из оригинал (PDF) на 2016-03-04. Получено 2009-12-19.
  2. ^ Микеланджело Гриньи (1995). «Полная лемма Спернера для PPA». Письма об обработке информации. 77 (5–6): 255–259. CiteSeerX  10.1.1.63.9463. Дои:10.1016 / S0020-0190 (00) 00152-6.
  3. ^ А. Филос-Рацикас, П.В. Гольдберг (2018). «Консенсус-сокращение вдвое - PPA-Complete». Proc. 50-го Симпозиум по теории вычислений. С. 51–64. arXiv:1711.04503. Дои:10.1145/3188745.3188880.
  4. ^ Э. Жержабек (2016). «Целочисленное разложение и модульные квадратные корни». Журнал компьютерных и системных наук. 82 (2): 380–394. arXiv:1207.5220. Дои:10.1016 / j.jcss.2015.08.001.