PPAD (complexitate)

În informatică teoretică , PPAD ( Polynomial Parity Arguments on Directed graphs ) este o clasă de complexitate introdusă de Christos Papadimitriou în 1994. Această clasă este importantă în teoria jocurilor algoritmice, deoarece conține problema calculării echilibrului Nash și această problemă a fost demonstrată - finalizat de Chen și Deng în 2005.

Definiție

Referințe

1. Christos Papadimitriou , „  Despre complexitatea argumentului parității și alte dovezi ineficiente ale existenței  ”, Journal of Computer and System Sciences , vol.  48, n o  3,1994, p.  498-532 ( DOI  10.1016 / S0022-0000 (05) 80063-7 , citiți online )
2. * Xi Chen și Xiaotie Deng (2006) „Reglarea complexității echilibrului Nash cu doi jucători” în Proc. 47 simp. Bazele informaticii  : 261-271 p. ( DOI : 10.1109 / FOCS.2006.69 ).  .