34
$\begingroup$

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?

Improve this question
$\endgroup$

5 Answers 5

Reset to default
29
$\begingroup$

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.

Improve this answer
$\endgroup$
8
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 10
    $\begingroup$ 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). $\endgroup$
    – Noam
    Aug 19, 2010 at 16:16
8
$\begingroup$

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

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

Improve this answer
$\endgroup$
0
2
$\begingroup$

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.

Improve this answer
$\endgroup$
-1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 8
    $\begingroup$ There are countless papers showing P=NP. I wouldn't consider it relevant until it is properly peer-reviewed and published. $\endgroup$
    – Emil Jeřábek
    Jan 28, 2017 at 16:46
  • 1
    $\begingroup$ 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. $\endgroup$
    – Thomas Klimpel
    Jan 29, 2017 at 9:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.