Класс сложности PPAD обычно определяется указанием того, что End-Of-The-Line является PPAD-завершенным.
End-Of-The-Line - это проблема поиска. Входные данные состоят из ориентированного графа, в котором у каждого узла максимальная и минимальная степени равны 1. Граф задается вычисляемой функцией полиномиального времени которая возвращает предшественника и преемника x . Кроме того, каждому дается узел v с преемником, но без предшественника. Найдите узел t ≠ v , у которого нет преемника или предшественника.
Недавно я услышал другое определение PPAD. Насколько я помню, это было основано на следующей проблеме.
Дан ориентированный граф (опять-таки заданный вычислимой функцией за полиномиальное время) и узел, чья внутренняя степень не равна его внешней степени. Найдите другой узел с этим свойством.
Очевидно, что End-Of-The-Line является частным случаем последней проблемы, но действительно ли последняя проблема труднее решить? У меня вопрос такой:
Завершены ли обе задачи для одного и того же класса сложности PPAD? Если да, то почему? Если нет, то какой класс сложности является результатом второй проблемы?