Re:2018 Fields Medal and Nevanlinna Prize Winners
by sometimesijust on Wednesday August 01, 2018 @07:52PM
(#17668135)
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?
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?