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