算法与计算机科学arxiv.org
市场有效当且仅当 P=NP（2010）
Markets are efficient if and only if P = NP (2010)
2012 — 2020，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这是 2010 年的一篇 arXiv 论文，标题主张「市场当且仅当 P=NP 时才是有效的」。作者用期权等金融工具构造「器件」，把 3-SAT 等 NP 难问题嵌入市场定价之中，试图论证：若市场价格能高效反映所有可得信息，就等于能用市场在多项式时间内求解 NP 难问题，从而推出 P=NP；反之若 P≠NP，则完美有效市场不可能存在。
为什么经久不衰：它把理论计算机科学最著名的未解难题与金融学最富争议的假说绑在一起，无论论证是否严谨，都是一个极好的思想实验，十几年来反复引发经济学与计算复杂性交叉的有趣讨论。
HN 评论精选
标题过于绝对，忽略了连续性近似、算法是否真被使用以及多项式/指数实际规模等三点局限。
这挺有趣，但标题有点太绝对了。有三点局限（很多关于 P=NP 的论文都有）：1. 市场仍可能是有效的，因为要引发 P vs NP 问题所需的场景非常复杂，尤其需要购买极其昂贵的不可分割物品，而在大多数情况下我们可以把股票之类当作连续量处理，误差很小。2. 市场只有在 P=NP 且我们知道如何在多项式时间内求解 NP 问题并真的去求解时才可能有效。标题让人以为只要 P=NP 市场就已经有效，这是不对的。3. 即使 P=NP，那个多项式也可能大到市场无法有效；反过来 P≠NP 但指数小到现实中市场仍可能有效。
CJefferson查看英文原文
While this is a fun, the title is a little strong. There are three limitations (whuch apply to many papers about P=NP). 1. The market could still be efficient, because the situations which must arise to cause P vs NP problems are very complicated. In particular thry require very expensive indivisible things to buy, whereas in most situations we can treat things like shares as continuous with only a small error. 2. Markets could be efficient if P=NP and we know how to solve NP probkems in P, and we do it. The title makes it sound like the market will already be efficient if P=NP, which isnt true. 3. Even if P=NP, the polynomial could still be big enough the market cant be efficient. Similarly, P could not equal NP but the expoenential be small enough markets can still be efficient in reality.
若论点成立，它反而支持哈耶克式「集中计算不可能」的观点，而非简单地证明市场失败。
大多数人把这篇读成「市场天生有缺陷」的证明，用来支持他们对市场经济的意识形态不信任。但我认为，如果作者的论点成立且 P 确实不等于 NP，这个结论对主张用另一种（通常更集中的）经济计算方式去扩充或取代市场经济的人反而是更大的问题。阿连德的 Cybersyn 就著名地使用线性规划（P）来集中「模拟」并改进常规市场机制。若作者论点成立，它其实是在支持哈耶克等人的经济计算问题论点：经济分配问题的有效计算是不可能的，市场那些有缺陷的动态很可能已是我们能负担得起的最佳近似。
zwww查看英文原文
Most people seem to read this as a proof that markets are inherently flawed and as lending support to their ideological distrust of market economies. I think that if the authors thesis holds true and p indeed != np, this kind of conclusion could spell an even bigger problem for those who advocate to agument or replace market economies with another, typically more centralized, form of economic calculation. Allende's cybersyn famously used linear programming (P) in order to centrally 'simulate' and improve upon more regular market mechanics. If the authors thesis holds I think it's actually an argument in favor of the economic calculation problem talking point of Hayek and the like: efficient calculation of economic distribution problems is impossible and flawed dynamics of the market are probably close to the best approximation we can afford.
证明只对精确解成立、构造过于任意，这种「NP 难」论证可以套到任何东西上，不能因此否定有效市场假说作为近似模型的价值。
这篇论文每次看到都让我感慨。它其实没提出或证明什么不明显的东西（还有跑题扯到无关内容的问题）。首先它做了件好笑的事：用期权构造器件、把 3-SAT「嵌入」进去，从而「证明」有效市场假说是 NP 难的。这没问题，只不过（a）我们通常不关心精确解（所以需要近似难度，而它没给出）；（b）我还能想出无数类似的显然例子！比如：我给出一个衍生品，若在给定时间前找到某个（已知必然存在的）NP 难问题的解，其价格就是 1 美元。这也会「证明 EMH 是 NP 难的」，因为显然该衍生品应定价 1 美元（问题按构造有解），所以任何人都应「显然」给它定价 1 美元。这就像说「生活是 NP 难的」。是啊，当然。但这不意味着我们做不好事、理性（如 EMH）不是分析行为的好用（虽不完美）工具。推到极端一切都会崩，因为模型是错的。
LolWolf查看英文原文
This paper just gets me every time I see it. It really doesn’t claim or do much that isn’t already quite obvious (it also has the other problem of going on completely unrelated tangents.) First, it does this funny thing where it “proves” that EMH (or market efficiency) is NP-hard, by building gadgets based on options and then using them to “embed” 3-SAT. This is fine except (a) we often don’t care about an exact solution (so we need approximation-hardness that isn’t shown) and (b) I can come up with millions of other obvious things like this! Here’s a silly one one: I give a derivative whose price is $1 if a solution (that is known to exist) to an NP-hard problem is found by a given time. This will “show the NP hardness of EMH” because obviously the derivative price should be 1 (the problem has a solution, by construction) and so anyone should “obviously” price it at $1. This is like saying “life is NP-hard.” Like, yeah, of course it is. That doesn’t mean we aren’t pretty good at doing the right thing and rationality (like EMH) is a good, if imperfect tool to analyze behavior. Taking it to its extreme then everything breaks, because the model is wrong. We don’t throw up our hands and quit because making real-life decisions is a sampling-hard, query-hard, and NP-hard problem (if all data is known), but a basic model of rationality would say that humans can “perfectly” solve it. (Which is obviously crazy, but we obviously don’t throw the assumption of rationality of agents out the window because of this.) Otoh, I am definitely of the opinion that some economists hold EMH as a “magical” axiom, but that’s a different story.
N 人纳什均衡求解本身已知是 NP 难的，这给出一个更一般的论证，也说明论文并非新洞见。
这篇报告对有志学术的人来说是个有趣的思维练习，但并非新颖洞见，而且对大多数「市场有效」的定义来说显然不成立。如果要玩学术上的「比高低」游戏，一个更一般的结果是：N>2 时的「最佳」或「多重」N 人纳什均衡本身已是 NP 难的。有效市场的含义将是每个参与者都有多项式时间算法求解这个 NP 难问题，因此 P=NP。
ericjang查看英文原文
The report, while a fun thought exercise for any aspiring academic, is not a novel insight, and is obviously untrue for most definitions of market efficiency. If we are going to play the academic one-upmanship game, a more general result that "best" or "multiple" N-player Nash Equilibria for N > 2 is already NP-hard. The implication of an efficient market would be if every player had a polynomial-time algorithm to solve the NP-hard problem, ergo P=NP. [1] https://people.csail.mit.edu/costis/simplified.pdf [2] https://www.quantamagazine.org/in-game-theory-no-clear-path-to-equilibrium-20170718/ [3] https://arxiv.org/abs/1104.3760#:~:text=Unlike%20general%20Nash%20equilibrium%2C%20which,as%20finding%20a%20planted%20clique.
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选