前些天和亮喝酒，亮说我博客很久没更新，后面又和亮说起博弈论，亮学政治学，博弈论是必修课程，而对于我而言，博弈论只能作为业余的爱好。下面便写写关于纳什均衡计算复杂度的问题。当然，以计算机科学的视角和以政治学的视角看博弈论，可能真的是横看成岭侧成峰，但学科分划本是人为，真正的科学应该是没有界限的。几乎可以肯定的是，亮又要痛骂我写些没人看懂的东西，哈，博弈论本来就博大精深，其实我自己也是不懂的：P

在过去的几十年中，博弈论一直是学术界的热门话题。经济学家和社会学家研究如何用博弈论来对人们的理性行为进行建模和分析；而对于数学家和计算机科学家而言，他们则往往着眼于如何设计寻找纳什均衡的算法。但是，到目前为止，除了一些特例（如二人零和博弈）以外，至今没有找到计算一般纳什均衡的高效算法（多项式时间）。

在各种各样的问题中，有这样一类问题被计算机科学家称为NP-hard问题，这类问题被普遍的认为是不存在多项式时间算法的（存在多项式时间算法的问题又被成为P问题）。所以，如果我们能够证明求纳什均衡问题是NP-hard，那么我们至少可以暂时放弃寻找高效算法的尝试。可惜经过很多年的努力，求解纳什均衡的问题是否是NP-hard也依然未被证明。

于是，计算机科学家们又再退而求其次，他们定义了PPAD问题，PPAD问题包括了P问题，同时又是NP问题的子集。目前已经有很多重要的，至今未找到多项式时间算法的问题被证明是PPAD问题。清华的Xi Chen和香港城大的Xiaotie Deng在今年的FOCS会议（理论计算机科学的最高级别会议）上发表的文章Settling the Complexity of 2-Player Nash-Equilibrium证明了二人博弈的混合策略均衡问题是PPAD-complete的。由于之前已经证明对三人及三人以上博弈的纳什均衡问题是PPAD-complete，因此，这篇文章在某种程度上解决了纳什均衡的计算复杂度问题。

证明纳什均衡问题是PPAD-complete的，意味着：第一，如果找到求纳什均衡的多项式时间算法，则其它所有的PPAD问题都有多项式时间算法，这个可能性看起来并不大；第二，如果纳什均衡问题是NP-hard，那么就有NP=coNP，这在大多数计算机科学家看来都是不可能的。因此，更有可能的是，纳什均衡问题既不存在多项式时间算法，也不是NP-hard。很多人相信这一事实，但证明它却是极其困难的，因为证明了这一事实即意味着证明了P不等于NP。而P是否等于NP是计算机科学最核心的问题，在很多人看来，这一问题要到下个世纪才有可能被解决。

    在不加限制条件的情况下证明一个可计算函数的复杂度下界是计算复杂性领域中最具挑战性的问题之一。从1949年Shannon证明一个随机函数具有巨大的线路复杂度（circuit complexity）以来，对于计算显性函数的无限制布尔函数电路的规模的下界问题的研究一直鲜有进展。1997年，Razborov和Rudich在他们的文章Natural Proofs中对这一现象作出解释，他们证明多数当前已有的证明下界的技术不能用于这样的下界问题。一个研究显性函数复杂性的方法是在问题之间进行归约，例如给出一个标准问题（如一个NP完全问题），然后证明我们所关心的计算问题不比这一标准问题容易。另一种方法是对计算模型加以限制，以克服固有的自然证明（Natural Proofs）的局限性，同时让模型足够强以便于刻划大量的“自然”算法。

                                                               ――M. Alekhnovich于普林斯顿高等数学研究院

对NP-Hard问题和NP-Complete问题的一个直观的理解就是指那些很难（很可能是不可能）找到多项式时间算法的问题. 因此一般初学算法的人都会问这样一个问题: NP-Hard和NP-Complete有什么不同? 简单的回答是根据定义, 如果所有NP问题都可以多项式归约到问题A, 那么问题A就是NP-Hard; 如果问题A既是NP-Hard又是NP, 那么它就是NP-Complete. 从定义我们很容易看出, NP-Hard问题类包含了NP-Complete类. 但进一步的我们会问, 是否有属于NP-Hard但不属于NP-Complete的问题呢? 答案是肯定的. 例如停机问题, 也即给出一个程序和输入, 判定它的运行是否会终止. 停机问题是不可判的, 那它当然也不是NP问题. 但对于SAT这样的NP-Complete问题, 却可以多项式归约到停机问题. 因为我们可以构造程序A, 该程序对输入的公式穷举其变量的所有赋值, 如果存在赋值使其为真, 则停机, 否则进入无限循环. 这样, 判断公式是否可满足便转化为判断以公式为输入的程序A是否停机. 所以, 停机问题是NP-Hard而不是NP-Complete.