Hacker News new | ask | show | jobs
by QML 2947 days ago
What does this mean for the class of PPAD-complete [1] problems?

Someone correct me if I'm wrong, but if 1. Nash Equilibrium ⊂ FNP 2. "Markets are efficient" => FNP ⊂ FP

How is this different from "FP = FNP if and only if P = NP" [2], which is a result already found?

[1] https://en.wikipedia.org/wiki/PPAD_(complexity) [2] https://en.wikipedia.org/wiki/FNP_(complexity)