PPAD (complexidade)

Na ciência da computação teórica , PPAD ( Polynomial Parity Arguments on Directed graphs ) é uma classe de complexidade introduzida por Christos Papadimitriou em 1994. Esta classe é importante na teoria dos jogos algorítmicos porque contém o problema de calcular um equilíbrio de Nash e este problema foi demonstrado PPAD -completo por Chen e Deng em 2005.

Definição

Referências

1. Christos Papadimitriou , “  Sobre a complexidade do argumento da paridade e outras provas ineficientes da existência  ”, Journal of Computer and System Sciences , vol.  48, n o  3,1994, p.  498-532 ( DOI  10.1016 / S0022-0000 (05) 80063-7 , leia online )
2. * Xi Chen e Xiaotie Deng (2006) “Resolvendo a complexidade do equilíbrio de Nash de dois jogadores” em Proc. 47th Symp. Foundations of Computer Science  : 261–271 p. ( DOI : 10.1109 / FOCS.2006.69 ).  .