Evidence that PPAD is hard?

Question

There is often-quoted philosophical justification for believing that P != NP even without proof. Other complexity classes have evidence that they are distinct, because if not, there would be "surprising" consequences (like the collapse of the polynomial hierarchy).

My question is, what is the basis for belief that the class PPAD is intractable? If there was a polynomial time algorithm for finding Nash equilibria, would this imply anything about other complexity classes? Is there a heuristic argument for why it should be hard?

Answer 1

PPAD is pretty "low" above P and not much would change in our understanding of complexity if it was shown equal to P (except that the few problems in PPAD would now be in P). The main "evidence" that PPAD!=P is an oracle separation, which is essentially equivalent to the combinatorial fact that no "black-box simulation" exists.

Answer 2

Buhrman et al. showed there is an oracle relative to which all TFNP functions are poly-time computable, yet the Polynomial Hierarchy is infinite. TFNP is a class which contains PPAD and its cousins. This is another result strengthening our sense that PPAD being easy would not generate unlikely consequences in complexity.

The paper is "Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?"

available on Lance Fortnow's website. It seems an earlier version of the paper was titled "Inverting onto functions and the polynomial hierarchy" (the new version is under this old name on Lance's site).

Answer 3

(I guess no one ever answered this older question with the newer results; here you go:)

• Assuming the existence of quasipolynomially-hard indistinguishability obfuscation and subexponentially-hard one-way functions, there are Nash equilibria that are hard to find (and thus, $\mathsf{PPAD}$ is hard): On the Cryptographic Hardness of Finding a Nash Equilibrium
• In fact, $\mathsf{PPAD}$-hardness can even be based on polynomially-hard compact public-key functional encryption and polynomially-hard one-way permutations: Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium

---

And here is yet another, even more recent, option for $\mathsf{PPAD}$-hardness, via private-key functional encryption: From Minicrypt to Obfustopia via Private-Key Functional Encryption

Answer 4

While this has been bumped anyway, maybe I can have the hubris to mention a heuristic that comes to mind.

An NP-complete problem is, given a circuit, is there an input that evaluates to True?

• This problem would clearly be easy if the input were represented "explicitly" as a list of input-output pairs, rather than "succinctly" as a circuit.

• The problem is clearly information-theoretically hard if the input is a black-box oracle function rather than a circuit (requires trying all inputs).

• The problem in separating P from NP, if true, lies in showing that programs can't dissect circuits efficiently.

PPAD-complete problems share some interesting characteristics here. If you think of End-of-the-Line, it is "given a succinctly-represented graph with some restrictions, and a source, find a sink". And it shares the above three points, I think.

Answer 5

This paper is relevant to this, in that it attempts to show that PPAD = P: https://arxiv.org/abs/1609.08934