3 ms·
"And even if it were real, it would only be efficient if P=NP." Because finding global optima is hard? I grant that, but: 1) things can be intractably hard e
by dllthomas 12y ago
"And even if it were real, it would only be efficient if P=NP."
Because finding global optima is hard? I grant that, but:
1) things can be intractably hard even if P=NP - O(n^10000) is in P, and there are complexity classes strictly harder than P (e.g. EXPTIME)), and since there are innumerable moves anyone could take out into the future "optimal resource distribution" could plausibly fall in EXPTIME.
2) Regardless, any single entity determining optimal resource distribution also needs to solve the same problem.
If you were saying something else, please clarify.
- warfangle 12y agoMy edit cited the paper in question, where the author shows how to use markets to solve NP-complete problems. Either markets are weak-form efficient and P=NP, or markets are not weak-form efficient and P≠NP.
- dllthomas 12y agoAh. Cute, but doesn't look like something that can actually be applied to the real world.
- warfangle 12y agoKind of like theoretical free markets.
- dllthomas 12y agoSnarky. The difference is that you can have a model that is not precise and which still makes useful predictions. You can't have a proof that's not precise and still proves P=NP. Note that it is not "the existence of free markets" that is assumed and breaks things, but the existence of free markets with a particular formulation of a particular property. As strictly defined there, weak-form efficiency also allows seems to allow FTL communication.