Доказательства того, что PPAD сложно?

32

Существует часто цитируемое философское обоснование полагать, что P! = NP даже без доказательств. Другие классы сложности имеют доказательства того, что они различны, потому что если нет, то будут «удивительные» последствия (например, крах полиномиальной иерархии).

Мой вопрос: на чем основано убеждение, что класс PPAD неразрешим? Если бы существовал алгоритм полиномиального времени для нахождения равновесий по Нэшу, означало бы это что-нибудь для других классов сложности? Есть ли эвристический аргумент, почему это должно быть сложно?

Аарон Рот
источник

Ответы:

28

PPAD довольно «низок» выше P и мало что изменит в нашем понимании сложности, если он будет показан равным P (за исключением того, что несколько проблем в PPAD теперь будут в P). Основным «доказательством» того, что PPAD! = P, является разделение оракула, что по существу эквивалентно комбинаторному факту, что «симуляции черного ящика» не существует.

Ноам
источник
8

Берман и соавт. показал, что существует оракул, относительно которого все функции TFNP вычисляются по времени, хотя полиномиальная иерархия бесконечна. TFNP - это класс, который содержит PPAD и его двоюродных братьев. Это еще один результат, укрепляющий наше чувство, что простота использования PPAD не приведет к маловероятным последствиям в плане сложности.

Статья «Разрушается ли полиномиальная иерархия, если функции на них обратимы?»

доступно на сайте Лэнса Фортноу. Похоже, что более ранняя версия статьи называлась «Инвертирование в функции и полиномиальную иерархию» (новая версия находится под этим старым именем на сайте Лэнса).

Энди Друкер
источник
10
Отслеживаемость TFNP была бы значительно более удивительной, чем способность PPAD, поскольку первая исключала бы существование односторонних перестановок, а также предполагала P = (пересечение NP coNP).
Ноам
8

(Я думаю, никто никогда не отвечал на этот старый вопрос с новыми результатами; вот так :)


А вот еще один, еще недавно, вариант для -hardness, с помощью частного ключа функционального шифрования: От Minicrypt к Obfustopia через частный ключ шифрование функциональногоппAD

Даниэль Апон
источник
2

Хотя в любом случае это столкнулось, возможно, я могу иметь высокомерие, чтобы упомянуть эвристику, которая приходит на ум.

NP-полная проблема в заданной цепи, есть ли вход, который оценивается как True?

  • Эта проблема, очевидно, была бы простой, если бы вход был «явно» представлен в виде списка пар ввода-вывода, а не «лаконично» в виде схемы.

  • Проблема явно информационно-теоретически трудна, если вход является функцией оракула черного ящика, а не цепью (требуется перепробовать все входы).

  • Проблема отделения P от NP, если она истинна, заключается в том, чтобы показать, что программы не могут эффективно анализировать схемы.

Задачи, полные PPAD, имеют некоторые интересные характеристики. Если вы думаете о «Конце строки», то ему «дано сжато представленный граф с некоторыми ограничениями и источником, найдите сток». И это разделяет три вышеупомянутых пункта, я думаю.

усул
источник
-1

Этот документ имеет отношение к этому, поскольку он пытается показать, что PPAD = P: https://arxiv.org/abs/1609.08934

Сэмюэль Шлезингер
источник
7
Есть бесчисленные документы, показывающие P = NP. Я не считаю это уместным, пока оно не будет должным образом проверено и опубликовано.
Эмиль Йержабек поддерживает Монику
Первая ошибка - последняя строка доказательства леммы 10 на странице 18, поскольку «f (alpha, eps) <0 для eps = 0 и lim_alpha f (alpha, eps) = бесконечность для eps> 0» не является невозможным, даже если f (альфа, эпсилон) является непрерывной функцией от альфа и эпсилона. Но поскольку в статье дается явный алгоритм, вам, безусловно, также нужен явный контрпример, где этот алгоритм дает сбой, прежде чем вы сможете утверждать, что опровергли эту статью.
Томас Климпел