3 ms·
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"
by QML 8y 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) https://en.wikipedia.org/wiki/PPAD_(complexity)
[2] https://en.wikipedia.org/wiki/FNP_(complexity) https://en.wikipedia.org/wiki/FNP_(complexity)