Почему эти два определения PPAD эквивалентны?

13

Класс сложности PPAD обычно определяется указанием того, что End-Of-The-Line является PPAD-завершенным.

End-Of-The-Line - это проблема поиска. Входные данные состоят из ориентированного графа, в котором у каждого узла максимальная и минимальная степени равны 1. Граф задается вычисляемой функцией полиномиального времени которая возвращает предшественника и преемника x . Кроме того, каждому дается узел v с преемником, но без предшественника. Найдите узел t v , у которого нет преемника или предшественника.f(x)xvtv

Недавно я услышал другое определение PPAD. Насколько я помню, это было основано на следующей проблеме.

Дан ориентированный граф (опять-таки заданный вычислимой функцией за полиномиальное время) и узел, чья внутренняя степень не равна его внешней степени. Найдите другой узел с этим свойством.


Очевидно, что End-Of-The-Line является частным случаем последней проблемы, но действительно ли последняя проблема труднее решить? У меня вопрос такой:

Завершены ли обе задачи для одного и того же класса сложности PPAD? Если да, то почему? Если нет, то какой класс сложности является результатом второй проблемы?

Матиас
источник

Ответы:

15

О проблемах с цитируемой статьей (и, следовательно, об этом ответе) см. Действительно ли PPAD отражает идею поиска другой несбалансированной вершины?

Да. Эти две проблемы эквивалентны и, следовательно, PPAD-завершены. Сокращение приведено на странице 505 оригинальной статьи Пападимитриу за 1994 год ( pdf ), в которой представлен конец строки . Это справедливо даже в том случае, если степень графа экспоненциальная, если нам дан «алгоритм распознавания ребер» и «функция сопряжения». Это также упоминается на той же странице. Сокращение дано для PPA (неориентированная версия PPAD). Его можно распространить и на PPAD.

Шива Кинтали
источник
3
У меня проблема с расширением аргумента на PPAD. В оригинальном доказательстве новые вершины создаются путем объединения пар ребер одной и той же старой вершины. Для PPAD кажется естественным объединить входящие и исходящие ребра. Но тогда больше не гарантируется, что каждая несбалансированная старая вершина производит только одну несбалансированную новую вершину. И если их много, поиск в новом графе может вернуть другую новую вершину, созданную той же старой вершиной. Это не дает ответа на исходную проблему. Как можно преодолеть эту проблему?
Даниил Мусатов