文章
Slash Boxes
评论

计算机科学家给经济学家的教诲——纳什均衡是NP问题

matrix 发表于 2009年11月10日 17时54分 星期二   Printer-friendly   Email story
来自经济学就是神神叨叨部门
数学 科学
以1994年诺贝尔经济学奖得主约翰·纳什命名的纳什均衡是博弈论中的重要概念。纳什证明每个博弈必定存在一个纳什均衡点，其他经济学则推测纳什均衡点极难找到，但如果找到的话，它将能精确描述市场的行为。那么找到纳什均衡点的难度究竟有多大呢？一位计算机科学博士生的博士论文(PDF)——获得2008年度美国计算机协会学位论文奖——认为经济学家的推测是错误的，找到纳什均衡点是几乎不可能的事。 目前担任MIT电机工程和计算机科学系助理教授的Constantinos Daskalakis与UC伯克利的Christos Papadimitriou、英国利物浦大学的Paul Goldberg合作，证明对某些博弈来说，穷全世界所有计算机之力，在整个宇宙寿命的时间内也计算不出纳什均衡点。Daskalakis相信，计算机找不到，人类也不可能找到。纳什均衡属于NP问题，Daskalakis证明它属于NP问题的一个子集，不是通常认为的NP-完全问题，而是PPAD-完全问题。这项研究成果被一些计算机科学家认为是十年来博弈论领域的最大进展。

«  微软审查Bing现金返还漏洞发现者 | 欧盟反对甲骨文收购Sun  »

相关文章

P/NP问题现状 3 条评论 [+]
《美国计算机学会通讯》第9期上，Lance Fortnow谈了当代的一个最基本的数学问题，随着计算机性能的提高，此问题的重要性也随之而上升。这一问题便是“P/NP问题”，这里的P指多项式时间（Polynomial），一个复杂问题如果能在多项式时间内解决，那么它便被称为P问题，这意味着计算机可以在有限时间内完成计算；NP指非确定性多项式时间（nondeterministic polynomial），一个复杂问题不能确定在多项式时间内解决，假如NP问题能找到算法使其在多项式时间内解决，也就是证得了P=NP。比NP问题更难的则是NP完全和NP-hard，如围棋便是一个NP-hard问题，有人证明它的必胜算法需要的計算量在10^600步以上，而宇宙中所有的原子数也不过是10^75，最强大的计算机恐怕也难以在多项式时间内求出答案。 P与NP问题是Steve Cook于1971年首次提出，在过去的40年里，计算机有了飞跃的发展，而数学家也提出了许多巧妙的算法，P/NP问题的进展到了何种地步？Fortnow说两个字可以总结：大门依然敞开（Still open）。他并不确信未来的量子计算机能解决NP完全问题；能解决NP完全，也不能保证能解决NP-hard。证明P=NP或P≠NP并不代表问题的开始或结束，越来越多的复杂问题还在前方。
This discussion has been archived. No new comments can be posted.
计算机科学家给经济学家的教诲——纳什均衡是NP问题 | 登录/创建一个账号 | 顶部 | 8 条评论 | 搜索讨论
显示选项 门槛:
声明: 下面的评论属于其发表者所有，不代表本站的观点和立场，我们不负责他们说什么。