PPAD (complexité)
En informatique théorique, PPAD (Polynomial Parity Arguments on Directed graphs) est une classe de complexité introduite par Christos Papadimitriou en 1994[1]. Cette classe est importante en théorie des jeux algorithmique car elle contient le problème de calculer un équilibre de Nash et ce problème a été démontré PPAD-complet par Chen et Deng en 2005[2].
Références
- Christos Papadimitriou, « On the complexity of the parity argument and other inefficient proofs of existence », Journal of Computer and System Sciences, vol. 48, no 3,‎ , p. 498–532 (DOI 10.1016/S0022-0000(05)80063-7, lire en ligne)
-
- Xi Chen et Xiaotie Deng « Settling the complexity of two-player Nash equilibrium » () (DOI 10.1109/FOCS.2006.69)
—Proc. 47th Symp. Foundations of Computer Science.
- Xi Chen et Xiaotie Deng « Settling the complexity of two-player Nash equilibrium » () (DOI 10.1109/FOCS.2006.69)
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.