Действительно ли PPAD отражает идею поиска другой несбалансированной вершины?

13

Класс сложности PPAD был изобретен Христосом Пападимитриу в его основополагающей статье 1994 года . Этот класс предназначен для охвата сложности задач поиска, когда существование решения гарантируется «аргументом четности в ориентированных графах»: если в ориентированном графе существует несбалансированная вершина, то должна существовать другая. Но обычно класс формально определяется в терминах ANOTHER END OF THE LINE ( AEOL) проблема, когда аргумент применяется только к графам как с внутренним, так и с конечным градусами 1 . Мой вопрос: почему эти понятия эквивалентны?

До этого момента это дубликат этого вопроса . Теперь я хочу сформулировать проблему формально и уточнить, почему я не удовлетворен ответом там.

Задача поиска ANOTHER UNBALANCED VERTEX ( AUV ): нам даны две схемы S и полиномиального размера, Pкоторые получают x{0,1}n и возвращает полиномиальный список других элементов в {0,1}n . Эти схемы определяют ориентированный графG=(V,E) гдеV={0,1}n и(x,y)E(yS(x)xP(y)) . Задача поиска заключается в следующем: даныS ,P иzV такие, чтоindegree(z)outdegree(z) , найти другую вершину с тем же свойством.

Задача поиска AEOL : то же самое, но и S и P возвращают либо пустой список, либо один элемент.

Понятие сводимости (корректируются в соответствии с предложением Рики): всего поиска проблема сводится к общей задаче поиска B с помощью полиномиальных функций F и г , если у является решение F ( х ) в задаче B предполагает г ( х , у ) является решение х в задаче А . ABfgyf(x)Bg(x,y)xA

Формальный вопрос : почему AUV сводится к AEOL ? Или мы должны использовать другое понятие сводимости?

Христос Пападимитриу доказывает аналогичную теорему о PPA (теорема 1, стр. 505), но аргумент, похоже, не работает для PPAD . Причина заключается в том, что вершина со степенью баланса будет преобразована в K вершины со степенью балансом ± 1 . Тогда алгоритм для A E O L может получить одну из этих вершин и вернуть другую. Это не даст новую вершину для A U V .±kk±1AEOLAUV

Ситуация ухудшается, потому что в всегда есть четное количество несбалансированных вершин, но в A U V их может быть нечетное количество. Вот почему нельзя построить биекцию между этими двумя наборами, и g не всегда может быть равно f - 1 . Если g ( x , f ( x ) ) x, то мы получим метод решения A U V за полиномиальное время хотя бы для некоторых случаев. Если г не зависит от х иAEOLAUVgf1g(x,f(x))xAUVgx для у 1у 2 , то у 2 может быть возвращенакачестве ответа на у 1 . Это не былодать решение для A U V .g(y1)=g(y2)y1y2y2y1AUV

Последний вопрос : можно ли как-то преодолеть перечисленные выше препятствия? Можно ли использовать возможную зависимость от x ?gx

Даниил Мусатов
источник
2
"Почему эти понятия эквивалентны?" По причинам, приведенным в доказательстве теоремы 1 на странице 505 Христосом Пападимитриу. (В противном случае, что, по вашему мнению, является аргументом четности для всей совокупности AUV?) Ваше определение сводимости кажется слишком сильным. Например, по вашему определению, расширение набора решений может сделать задачу полного поиска строго сложнее.
2
+1 и -1 имеют одинаковое соотношение. (Это соотношение "странно".)Правильный имеет "подразумевает "вместо", если г (g(x,y) ».g(y)
2
Теперь то, что у нас есть, это то, что я назову это UnbalancedInOtherDirectionVertex, эта проблема сводится к PPADS , так как можно перевернуть края, если необходимо, чтобы у данной вершины был больший уклон, чем у уклонения, а затем всего -degree-1 вершины, в которые превращается данная вершина, будут источниками, а не стоками. Я не вижу аналогичного пути перехода от вашей проблемы к AEOL. k
1
По крайней мере, сокращение показывает, что AUV эквивалентно его случаю, когда все вершины имеют степень и степень не более 1, за исключением, возможно, для данной вершины z, которая имеет степень 0, но может иметь большую степень.
Эмиль Йержабек
2
Я только что услышал от Фредерика Менье, что он также наблюдал эту проблему пять лет назад, и Пападимитриу согласился.
domotorp

Ответы:

4

Было доказано, что проблемы эквивалентны (и, следовательно, PPAD-завершены), см. Раздел 8 в «Задаче о волосатом шаре - PPAD-Complete» Пола В. Голдберга и Александроса Холлендера .

domotorp
источник
1
Благодарю. Оказывается, что доказательство появилось в более раннем техническом отчете тех же авторов: «Сложность многоисточниковых вариантов задачи конца строки и краткая изуродованная шахматная доска»
Даниил Мусатов
4

Это интересный вопрос, и я могу дать только частичный ответ.

Нетрудно видеть, что конструкция на с. 505 из статьи Пападимитриу показывает эквивалентность AUV с его частным случаем

МНОГИЕ КОНЕЦ ЛИНИИ (MEOL): Для ориентированного графа с не более чем 1 градусом в градусах и градусах (представленными схемами, как указано выше) и непустым множеством X источников G , найдите сток или источник v. X .G1XGvX

С одной стороны, мне трудно представить преобразование таких графов, которое могло бы сократить большее количество источников до одного.

Однако, с другой стороны, MEOL относится ко всем обычно изучаемым классам, содержащим PPAD, за исключением, возможно, самого PPAD :

Во-первых, очевидно,

MEOL находится в PPADS .

Ниже я приведу набросок

МЕОЛ в ППА

G=(V,E)X

|X|XX

s=|X|2k2sG=(V,E)2kVA,BV(A,B)EA={a0,,a2k1}B={b0,,b2k1}(ai,bi)Ei<2k

G1AVGAAX1

At=|AX|0<t2kt=2k=|A|AX(s2k)p(ab)b+(ab)=apkиз этого следует, что нечетно. Более того, существуют биекции за полиномиальное время между и -элементными подмножествами . Используя это, мы можем определить соответствие полиномиальное время на всех , кроме одного из - элементных подмножеств . Мы включили его в график, который уменьшает количество известных источников с до .(s2k)[0,(ab))b[0,a)2kXt=2k1

Для формула подсчета переносов показывает, что является четным. Опять же , мы можем найти явное соответствие на - элементных подмножеств . Мы распространяем его на известные источники с , применяя сопоставление к и оставляя фиксированным.0<t<2k tXA| AX| =tAXAX(st)tXA|AX|=tAXAX

Таким образом, мы создаем неориентированный граф с одной известной листовой вершиной. Мы запрашиваем у оракула PPA еще один лист, и по построению мы можем извлечь из него ответ для экземпляра MEOL .


Как кратко упомянул Пападимитриу, мы можем обобщить PPA на классы PPA - для любого простого числа . Пример полной проблемы PPA -р рppp

AUV - : для заданного ориентированного графа и вершины с балансом степени найдите другую такую ​​вершину.GpG0(modp)

(См. Этот ответ для эквивалентности AUV - с определением PPA Пападимитриу - .)pp

ППА - это просто ППА . Предполагается, что классы PPA - попарно несопоставимы и несопоставимы с PPADS . Все они включают PPAD .2p

В аргументе, который я изложил выше, ничего особенного в , и его можно легко изменить, чтобы получитьp=2

MEOL находится в PPA - для каждого простого .pp

Эмиль Йержабек
источник
Мне очень нравится ответ, и я решил принять его (конечно, более полные ответы все еще приветствуются). Я только думаю , что класс представлен АНП - следует называть PPAD - . Пападимитриу пишет о неориентированных двудольных графах и просто градусах, а не балансах. pp
Даниил Мусатов
3
Классы являются обобщениями PPA, а не PPAD, для . Пападимитриу дает другую полную задачу, чем AUV- (обратите внимание, что его графики двудольные), но это эквивалентно моему определению. Вся схема именования очень запутанная; использование ориентированных и неориентированных графов для определенного класса является просто случайностью, у многих классов есть полные проблемы, касающиеся как ориентированных, так и неориентированных графов (как в случае PPA- ). Кроме того, несмотря на их имена, большинство классов основаны не на аргументах четности, а на других принципах подсчета. Только ППА о паритете. p=2pp
Эмиль Йержабек
Спасибо, получил его. Это действительно тот же класс. Я слышал предположение, что Пападимитриу выбрал имя PPAD, потому что оно напоминает его собственную фамилию.
Даниил Мусатов
У вас есть ссылка на PPAD в PPA-p?
domotorp
1
Не явный, но, например, определяющая PPAD-полная проблема буквально является частным случаем AUV- . p
Эмиль Йержабек