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

<ul>
<li>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): <a href="https://eprint.iacr.org/2014/1029.pdf" rel="nofollow noreferrer">On the Cryptographic Hardness of Finding a Nash Equilibrium</a></li>
<li>In fact, $\mathsf{PPAD}$-hardness can even be based on <em>polynomially-hard</em> compact public-key functional encryption and <em>polynomially-hard</em> one-way permutations: <a href="https://eprint.iacr.org/2015/1078.pdf" rel="nofollow noreferrer">Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium</a></li>
</ul>

<hr>

<p>And here is yet another, even more recent, option for $\mathsf{PPAD}$-hardness, via <em>private-key</em> functional encryption: <a href="https://eprint.iacr.org/2017/080" rel="nofollow noreferrer">From Minicrypt to Obfustopia via Private-Key Functional Encryption</a></p>

CC BY-SA 3.0
2017-02-05T13:59:13.357Z
2017-02-07T19:07:51.287Z
2017-02-07T19:07:51.287Z
Daniel Apon
<p>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.</p>

<p>The paper is 
"Does the Polynomial Hierarchy Collapse if Onto
Functions are Invertible?"</p>

<p>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).</p>

CC BY-SA 2.5
2010-08-19T16:16:17.883Z
The tractability of TFNP would be significantly more surprising than that of PPAD since the former would rule out the existence of 1-way permutations as well as imply P=(NP intersection coNP).
Noam
CC BY-SA 2.5
2010-08-19T15:52:32.113Z
2010-08-19T15:52:32.113Z
Andy Drucker
<p>While this has been bumped anyway, maybe I can have the hubris to mention a heuristic that comes to mind.</p>

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

<ul>
<li><p>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.</p></li>
<li><p>The problem is clearly information-theoretically hard if the input is a black-box oracle function rather than a circuit (requires trying all inputs).</p></li>
<li><p>The problem in separating P from NP, if true, lies in showing that programs can't dissect circuits efficiently.</p></li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2017-01-30T00:15:50.980Z
2017-01-30T00:15:50.980Z
usul
<p>This paper is relevant to this, in that it attempts to show that PPAD = P: <a href="https://arxiv.org/abs/1609.08934" rel="nofollow noreferrer">https://arxiv.org/abs/1609.08934</a></p>

CC BY-SA 3.0
2017-01-28T16:46:06.777Z
There are countless papers showing P=NP. I wouldn't consider it relevant until it is properly peer-reviewed and published.
Emil Jeřábek
CC BY-SA 3.0
2017-01-29T09:11:05.300Z
The first error is the last line of the proof of Lemma 10 on page 18, since "f(alpha, eps) < 0 for eps=0 and lim_alpha f(alpha, eps) = infinity for eps > 0" is not impossible, even if f(alpha, epsilon) is a continuous function from alpha and epsilon. But since the paper gives an explicit algorithm, you certainly also want an explicit counterexample where that algorithm fails, before you can claim that you refuted that paper.
Thomas Klimpel
CC BY-SA 3.0
2017-01-28T16:02:26.833Z
2017-01-28T16:02:26.833Z
Samuel Schlesinger
<p>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.</p>

CC BY-SA 2.5
2010-08-19T15:30:35.467Z
2010-08-19T15:30:35.467Z
Noam
<p>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). </p>

<p>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? </p>

<cc.complexity-theory><complexity-classes><gt.game-theory><conditional-results>
Evidence that PPAD is hard?
Aaron Roth
# Evidence that PPAD is hard?

(Asked by: username_0 on 2010-08-19)

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?

**Tags:** cc.complexity-theory, complexity-classes, gt.game-theory, conditional-results


---

## 5 answers

### Answer by username_3 on 2010-08-19. Score: 29 | Accepted answer

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 by username_1 on 2017-02-05. Score: 8

(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](https://eprint.iacr.org/2014/1029.pdf)
* 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](https://eprint.iacr.org/2015/1078.pdf)

---

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](https://eprint.iacr.org/2017/080)


---

### Answer by username_2 on 2010-08-19. Score: 8

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).

> **Comments:**
> **username_3**: The tractability of TFNP would be significantly more surprising than that of PPAD since the former would rule out the existence of 1-way permutations as well as imply P=(NP intersection coNP).  

---

### Answer by username_4 on 2017-01-30. Score: 2

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 by username_5 on 2017-01-28. Score: -1

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

> **Comments:**
> **username_6**: There are countless papers showing P=NP. I wouldn't consider it relevant until it is properly peer-reviewed and published.  
> **username_7**: The first error is the last line of the proof of Lemma 10 on page 18, since "f(alpha, eps) < 0 for eps=0 and lim_alpha f(alpha, eps) = infinity for eps > 0" is not impossible, even if f(alpha, epsilon) is a continuous function from alpha and epsilon. But since the paper gives an explicit algorithm, you certainly also want an explicit counterexample where that algorithm fails, before you can claim that you refuted that paper.  

---

