32
$\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?

$\endgroup$
28
$\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.

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

$\endgroup$
  • 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 '10 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

$\endgroup$
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.

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
  • 7
    $\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 supports Monica Jan 28 '17 at 16:46
  • $\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 '17 at 9:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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