以1994年诺贝尔经济学奖得主约翰·纳什命名的纳什均衡是博弈论中的重要概念。纳什证明每个博弈必定存在一个纳什均衡点，其他经济学则推测纳什均衡点极难找到，但如果找到的话，它将能精确描述市场的行为。那么找到纳什均衡点的难度究竟有多大呢？MIT的一位计算机科学博士生的博士论文(PDF)——获得2008年度美国计算机协会学位论文奖——认为经济学家的推测是错误的，找到纳什均衡点是几乎不可能的事。

目前担任MIT电机工程和计算机科学系助理教授的Constantinos Daskalakis与UC伯克利的Christos Papadimitriou、英国利物浦大学的Paul Goldberg合作，证明对某些博弈来说，穷全世界所有计算机之力，在整个宇宙寿命的时间内也计算不出纳什均衡点。Daskalakis相信，计算机找不到，人类也不可能找到。纳什均衡属于NP问题，Daskalakis证明它属于NP问题的一个子集，不是通常认为的NP-完全问题，而是PPAD-完全问题。这项研究成果被一些计算机科学家认为是十年来博弈论领域的最大进展。