2015-03-02-markets-efficient-iff-p-np

原文链接 http://arxiv.org/pdf/1002.2284v2.pdf

读的时候，作者在讨论P=NP问题的时候提到，如果P=NP那么很多不可思议的事情会发生。这其实也蛮好理解的：大数分解等其他计算难题被攻破，电子信用体系将瓦解。我想到的是这样的例子。不过研究人员们显然对这个问题的跨界有着更多地思考，比如这篇： 市场是有效的当且仅当P=NP。 这不是那种数学公式漫天飞得论文，更像是文艺经济学家写的那种论文。 用大量的笔触描写P=NP这个问题和市场有效性之间的关系。 如果你期待这篇论文对市场有效进行了如何惊人的建模，如何数学地证明了市场有效和P=NP问题之间的等价性，（像原来的我） 那这篇论文不是你的菜。 如果你觉得脑洞打开，“居然有人能把这两样东西联系起来，快看看他说些什么呢？”， 请接着往下看：

一下为我对这篇脑洞大开的论文的摘要和总结：

市场有效性的定义和分类主要围绕信息论展开。 传统上讲市场有效分为：弱有效（历史价格），半强有效（所有公开信息），强有效（未公开信息）。 对市场有效性的研究主要集中在：回报预测，事件研究， 未公开信息测试。 对回报预测的新研究方法不仅包含了对历史价格的使用，同时还包含了对：股息，利率，市值等变量的使用。

假设有n个历史价格变动，每个变动要么Up要么Down，假设有三种交易策略：买/卖/持有。 那么在这N个历史价格波动上总共可能有3^N个交易策略。 问题1： 是否存在统计意义上的策略能够持续盈利？ 问题的答案要测试3^n个可能的策略， 该问题为NP因为确认答案要花多项式时间。 随着资产历史的积累， 不管是引入更加细化的数据还是如何，市场总归是变得更加无效， 因为更多地数据总归意味着更多地分析时间。

问题2：给定一个固定的时间窗口t是否存在买入或卖出策略能够在统计意义下稳定的盈利？ 注意这里的买入卖出策略可以理解成策略的策略，即是否使用指定的策略。

问题3：给定一个时间窗口t和指定盈利值K是否存在一个买入卖出策略S能够在时间窗口t下产生超过指定利润K？

对于这些问题没有简单的回答，验证一个策略产生了多少利润可以在常数时间内完成，但是寻找这样的策略却是消耗指数时间的。

问题4： 问题3 + 给定一个预算B，并且这样的策略没有超出预算B

问题4和背包问题是很相似的，实际上是等价的。并且已经知道背包问题是NP完全的。 如果P=NP那么可以从这些问题得出市场是有效的结论，因为投资者总是能够通过背包问题问题的高效的算法找到问题4的解，从而使得市场有效（价格反应了所有信息）。

P=NP 推出 市场是有效的 从概念上理解起来似乎也并不困难， 注意论文的题目是当且仅当， 那么反过来推： 当市场是有效的，如何推出P=NP呢？ 这就是亮点了。

首先是一些基本构造： OCO：order-cancel-order 当一个订单被满足的时候另外一个订单立刻被撤销。 注意不会出现两个订单同时被满足。 同时定义OCO-3，这种新的操作能够同时操作3种资产 （就是为了跟3-SAT相对应而已）， 这些基本构造也就导出了市场计算器想要尝试解决的问题:NPC 3-SAT.

市场计算版3-SAT问题： 每个变量都对应了一种证券标的， 变量本身表示了买入单，取反的变量表示了卖出单， 那么3-SAT里的每一个单元都对应了市场上得OCO-3订单。 那么市场应该做什么呢？如果市场真的是有效的，那么市场上就会存在着一种执行这些OCO-3订单的方法，并且这些订单会产生利润，哪怕计入手续费等。 也就是说，市场允许我们在多项式时间内计算任意的3-SAT 问题。

小结一下： 证明的过程并不是十分符号化，我个人觉得充斥着很多：就是这样啦，你懂的之类的语句。 不过值得注意的倒是这种比对的思路本身，我相信P=NP和市场有效性确实是相关的。