PPAD
有向图的多项式校验参数
条目
美国加州大学伯克利分校的克里斯托斯·帕帕迪米特里欧(Christos Papadimitriou) 教授定义了PPAD（polynomial parity arguments on directed graphs，有向图的多项式校验参数）计算复杂类来描述经济学中的计算问题。
正文
经济学中的计算问题
计算无处不在，任何一门成熟的学科都涉及一些计算问题，在经济学中，这样的概念尤其多。以经
济学中的最基本概念“纳什均衡”以及“市场均衡”的计算为例，它们与传统计算机科学中所研究的计算问题存在很大区别：它们不是判定问题，纳什均衡点的存在性是有纳什定理直接保证的；它们也不是优化问题，因为没有一个优化的目标。从本质上讲，它们是一类不动点的计算问题，所以从传统的NP-Complete（non-deterministic polynomial，非确定多项式完全问题）角度来研究他们的计算复杂度并不合适。为此，美国加州大学伯克利分校的克里斯托斯·帕帕迪米特里欧(Christos Papadimitriou) 教授定义了PPAD（polynomial parityarguments on directed graphs，有向图的多项式校验参数）计算复杂类来描述这类问题，并与其合作者一起证明了在4 人及以上的博弈中，纳什均衡的计算是属于PPAD-Complete 的。哥伦比亚大学的陈汐教授和上海交通大学的邓小铁教授把结果加强到二人博弈的纳什均衡的计算也是属于PPAD-Complete 的。