Класс сложности PPAD был изобретен Христосом Пападимитриу в его основополагающей статье 1994 года . Этот класс предназначен для охвата сложности задач поиска, когда существование решения гарантируется «аргументом четности в ориентированных графах»: если в ориентированном графе существует несбалансированная вершина, то должна существовать другая. Но обычно класс формально определяется в терминах ( ) проблема, когда аргумент применяется только к графам как с внутренним, так и с конечным градусами . Мой вопрос: почему эти понятия эквивалентны?
До этого момента это дубликат этого вопроса . Теперь я хочу сформулировать проблему формально и уточнить, почему я не удовлетворен ответом там.
Задача поиска ( ): нам даны две схемы и полиномиального размера, которые получают и возвращает полиномиальный список других элементов в . Эти схемы определяют ориентированный граф где и . Задача поиска заключается в следующем: даны , и такие, что , найти другую вершину с тем же свойством.
Задача поиска : то же самое, но и и возвращают либо пустой список, либо один элемент.
Понятие сводимости (корректируются в соответствии с предложением Рики): всего поиска проблема сводится к общей задаче поиска B с помощью полиномиальных функций F и г , если у является решение F ( х ) в задаче B предполагает г ( х , у ) является решение х в задаче А .
Формальный вопрос : почему сводится к ? Или мы должны использовать другое понятие сводимости?
Христос Пападимитриу доказывает аналогичную теорему о PPA (теорема 1, стр. 505), но аргумент, похоже, не работает для PPAD . Причина заключается в том, что вершина со степенью баланса будет преобразована в K вершины со степенью балансом ± 1 . Тогда алгоритм для A E O L может получить одну из этих вершин и вернуть другую. Это не даст новую вершину для A U V .
Ситуация ухудшается, потому что в всегда есть четное количество несбалансированных вершин, но в A U V их может быть нечетное количество. Вот почему нельзя построить биекцию между этими двумя наборами, и g не всегда может быть равно f - 1 . Если g ( x , f ( x ) ) ≠ x, то мы получим метод решения A U V за полиномиальное время хотя бы для некоторых случаев. Если г не зависит от х и для у 1 ≠ у 2 , то у 2 может быть возвращенакачестве ответа на у 1 . Это не былодать решение для A U V .
Последний вопрос : можно ли как-то преодолеть перечисленные выше препятствия? Можно ли использовать возможную зависимость от x ?
источник
Ответы:
Было доказано, что проблемы эквивалентны (и, следовательно, PPAD-завершены), см. Раздел 8 в «Задаче о волосатом шаре - PPAD-Complete» Пола В. Голдберга и Александроса Холлендера .
источник
Это интересный вопрос, и я могу дать только частичный ответ.
Нетрудно видеть, что конструкция на с. 505 из статьи Пападимитриу показывает эквивалентность AUV с его частным случаем
С одной стороны, мне трудно представить преобразование таких графов, которое могло бы сократить большее количество источников до одного.
Однако, с другой стороны, MEOL относится ко всем обычно изучаемым классам, содержащим PPAD, за исключением, возможно, самого PPAD :
Во-первых, очевидно,
Ниже я приведу набросок
Для формула подсчета переносов показывает, что является четным. Опять же , мы можем найти явное соответствие на - элементных подмножеств . Мы распространяем его на известные источники с , применяя сопоставление к и оставляя фиксированным.0<t<2k tXA| A∩X| =tA∩XA∖X(st) t X A |A∩X|=t A∩X A∖X
Таким образом, мы создаем неориентированный граф с одной известной листовой вершиной. Мы запрашиваем у оракула PPA еще один лист, и по построению мы можем извлечь из него ответ для экземпляра MEOL .
Как кратко упомянул Пападимитриу, мы можем обобщить PPA на классы PPA - для любого простого числа . Пример полной проблемы PPA -р рp p p
(См. Этот ответ для эквивалентности AUV - с определением PPA Пападимитриу - .)p p
ППА - это просто ППА . Предполагается, что классы PPA - попарно несопоставимы и несопоставимы с PPADS . Все они включают PPAD .2 p
В аргументе, который я изложил выше, ничего особенного в , и его можно легко изменить, чтобы получитьp=2
источник