Preuve que PPAD est difficile?

Il y a une justification philosophique souvent citée pour croire que P! = NP même sans preuve. D'autres classes de complexité ont la preuve qu'elles sont distinctes, car sinon, il y aurait des conséquences "surprenantes" (comme l'effondrement de la hiérarchie polynomiale).

Ma question est, quelle est la base pour croire que la classe PPAD est insoluble? S'il y avait un algorithme polynomial de temps pour trouver les équilibres de Nash, cela impliquerait-il quoi que ce soit d'autre classes de complexité? Existe-t-il un argument heuristique pour expliquer pourquoi cela devrait être difficile?

PPAD est assez "bas" au-dessus de P et peu de choses changeraient dans notre compréhension de la complexité si elle était montrée égale à P (sauf que les quelques problèmes dans PPAD seraient maintenant dans P). La principale "preuve" que PPAD! = P est une séparation d'oracle, qui est essentiellement équivalente au fait combinatoire qu'aucune "simulation de boîte noire" n'existe.

Buhrman et al. a montré qu'il existe un oracle par rapport auquel toutes les fonctions TFNP sont calculables en temps poly, mais la hiérarchie polynomiale est infinie. TFNP est une classe qui contient PPAD et ses cousins. C'est un autre résultat renforçant notre sentiment que PPAD étant facile ne générerait pas de conséquences improbables en termes de complexité.

Le document est "La hiérarchie polynomiale s'effondre-t-elle si les fonctions sur sont inversibles?"

disponible sur le site Web de Lance Fortnow. Il semble qu'une version antérieure du document était intitulée "Inverser sur les fonctions et la hiérarchie polynomiale" (la nouvelle version est sous cet ancien nom sur le site de Lance).

(Je suppose que personne n'a jamais répondu à cette question plus ancienne avec les résultats les plus récents; c'est parti :)

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

$\mathsf{PPAD}$

Bien que cela ait été heurté de toute façon, je peux peut-être avoir l'orgueil de mentionner une heuristique qui me vient à l'esprit.

Un problème NP-complet est, étant donné un circuit, y a-t-il une entrée qui vaut True?

• Ce problème serait clairement facile si l'entrée était représentée "explicitement" comme une liste de paires entrée-sortie, plutôt que "succinctement" comme un circuit.

• Le problème est clairement théoriquement difficile si l'entrée est une fonction oracle de boîte noire plutôt qu'un circuit (nécessite d'essayer toutes les entrées).

• Le problème de la séparation de P de NP, s'il est vrai, consiste à montrer que les programmes ne peuvent pas disséquer efficacement les circuits.

Les problèmes liés à PPAD partagent ici des caractéristiques intéressantes. Si vous pensez à End-of-the-Line, il est "donné un graphique succinctement représenté avec quelques restrictions, et une source, trouvez un puits". Et il partage les trois points ci-dessus, je pense.

Ce document est pertinent à cet égard, en ce qu'il tente de montrer que PPAD = P: https://arxiv.org/abs/1609.08934