Dowód, że PPAD jest trudny?

Często cytowane jest filozoficzne uzasadnienie, by wierzyć, że P! = NP nawet bez dowodu. Inne klasy złożoności mają dowody na ich odrębność, ponieważ jeśli nie, miałyby „zaskakujące” konsekwencje (takie jak upadek hierarchii wielomianowej).

Moje pytanie brzmi: jaka jest podstawa przekonania, że ​​klasa PPAD jest trudna do rozwiązania? Gdyby istniał algorytm wielomianowy do znajdowania równowagi Nasha, czy oznaczałoby to cokolwiek w innych klasach złożoności? Czy istnieje heurystyczny argument za tym, dlaczego powinno to być trudne?

PPAD jest dość „niski” powyżej P i niewiele zmieniłoby się nasze rozumienie złożoności, gdyby wykazano, że jest równe P (poza tym, że kilka problemów w PPAD byłoby teraz w P). Głównym „dowodem”, że PPAD! = P jest separacją wyroczni, co jest zasadniczo równoważne z kombinatorycznym faktem, że nie istnieje „symulacja czarnej skrzynki”.

Buhrman i in. pokazał, że istnieje wyrocznia, w stosunku do której wszystkie funkcje TFNP są obliczalne w czasie wielowymiarowym, jednak Hierarchia Wielomianowa jest nieskończona. TFNP to klasa zawierająca PPAD i jego kuzynów. To kolejny wynik wzmacniający nasze przekonanie, że łatwość PPAD nie spowodowałaby mało prawdopodobnych konsekwencji w złożoności.

Artykuł brzmi: „Czy hierarchia wielomianowa zawali się, jeśli funkcje na są odwracalne?”

dostępny na stronie internetowej Lance Fortnow. Wydaje się, że wcześniejsza wersja artykułu nosiła tytuł „Odwracanie na funkcje i hierarchia wielomianowa” (nowa wersja nosi tę starą nazwę na stronie Lance'a).

(Chyba nikt nigdy nie odpowiedział na to starsze pytanie z nowszymi wynikami; proszę bardzo :)

• $\mathsf{PPAD}$
• $\mathsf{PPAD}$

$\mathsf{PPAD}$

Chociaż i tak zostało to podważone, może uda mi się nakłonić pychę do wspomnienia o heurystyce, która przychodzi mi na myśl.

Problemem NP-complete jest, biorąc pod uwagę obwód, czy jest dane wejściowe, które dają wynik True?

• Problem ten byłby oczywiście prosty, gdyby dane wejściowe były reprezentowane „jawnie” jako lista par wejście-wyjście, a nie „zwięźle” jako obwód.

• Problem jest wyraźnie trudny teoretycznie, jeśli wejście jest funkcją wyroczni czarnej skrzynki, a nie obwodem (wymaga wypróbowania wszystkich wejść).

• Problem oddzielenia P od NP, jeśli jest prawdziwy, polega na tym, że programy nie potrafią skutecznie rozdzielić obwodów.

Problemy z kompletnym PPAD mają tutaj kilka interesujących cech. Jeśli myślisz o End-of-the-Line, to „otrzymujesz zwięźle przedstawiony wykres z pewnymi ograniczeniami i źródło, znajdź ujście”. I myślę, że podziela powyższe trzy punkty.

Niniejszy artykuł jest do tego istotny, ponieważ próbuje pokazać, że PPAD = P: https://arxiv.org/abs/1609.08934