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?
Re:2018 Fields Medal and Nevanlinna Prize Winners
by mygo on Wednesday August 01, 2018 @09:06PM
(#17668495)
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?
The decision problem for Nash Equilibria might be, does a second equilibrium exist?