5 ms·

How do PPAD-complete problems relate to P=NP/NP-complete problems/etc., if they do at all? Your description of PPAD-complete problems reminds me a lot of descri

How do PPAD-complete problems relate to P=NP/NP-complete problems/etc., if they do at all? Your description of PPAD-complete problems reminds me a lot of descriptions I've read of NP-related problems, but this is the first time I've heard of the term "PPAD".

cs702 8y ago
Very -- very! -- informally: in PPAD-complete problems, a solution is known to exist (e.g., there is always a Nash equilibrium), but no one knows of an efficient algorithm for finding the solution. In other complexity classes widely believed to be intractable, such as NP-complete, the problems are decision problems that ask a yes/no question, and no one knows of an efficient algorithm for answering the question. By "efficient algorithm," I again mean an algorithm whose running time is bounded by a polynomial function of input or problem size.
- mygo 8y ago
  so I guess, one way to put it, is to look at the Traveling Salesman Problem? The decision problem asks “given a set of cities is there a tour shorter than length n?”. This is NP-Complete. However the pop culture version of the problem is “given a set of cities, what is a tour of the shortest possible length?”. This would be the PPAD-complete version of the problem, since that solution does exist, it’s just unknown and not known to be tractable within polynomial time? Can the Nash Equilibrium problem have a decision version whose answer is either true or false?
  - sometimesijust 8y ago
    TSP is NP-hard for optimisation version and NP-complete for decision version. Consider how you would test that a minimal solution is minimal vs testing whether a given solution has less than a given cost. PPAD is less complete than these two classes. The decision problem for Nash Equilibria might be, does a second equilibrium exist?
    - mygo 8y ago
      Aah gotcha. So you’re saying it’s easier to verify the solution to a Nash equilibrium problem than it is to verify the solution to the TSP optimization problem?

cs702 8y ago

Very -- very! -- informally: in PPAD-complete problems, a solution is known to exist (e.g., there is always a Nash equilibrium), but no one knows of an efficient algorithm for finding the solution. In other complexity classes widely believed to be intractable, such as NP-complete, the problems are decision problems that ask a yes/no question, and no one knows of an efficient algorithm for answering the question. By "efficient algorithm," I again mean an algorithm whose running time is bounded by a polynomial function of input or problem size.

mygo 8y ago
so I guess, one way to put it, is to look at the Traveling Salesman Problem? The decision problem asks “given a set of cities is there a tour shorter than length n?”. This is NP-Complete. However the pop culture version of the problem is “given a set of cities, what is a tour of the shortest possible length?”. This would be the PPAD-complete version of the problem, since that solution does exist, it’s just unknown and not known to be tractable within polynomial time? Can the Nash Equilibrium problem have a decision version whose answer is either true or false?
- sometimesijust 8y ago
  TSP is NP-hard for optimisation version and NP-complete for decision version. Consider how you would test that a minimal solution is minimal vs testing whether a given solution has less than a given cost. PPAD is less complete than these two classes. The decision problem for Nash Equilibria might be, does a second equilibrium exist?
  - mygo 8y ago
    Aah gotcha. So you’re saying it’s easier to verify the solution to a Nash equilibrium problem than it is to verify the solution to the TSP optimization problem?