PPAD (kompleksitet)

I teoretisk informatikk , PPAD ( Polynom Paritet Argumenter om rettede grafer ) er en kompleksitet klasse introdusert av Christos Papadimitriou i 1994. Denne klassen er viktig i algoritmisk spillteori Nash likevekt og dette problemet har blitt demonstrert PPAD -komplett av Chen og Deng i 2005.

Definisjon

Referanser

1. Christos Papadimitriou , “  Om paritetsargumentets kompleksitet og andre ineffektive bevis for eksistens  ”, Journal of Computer and System Sciences , vol.  48, n o  3,1994, s.  498-532 ( DOI  10.1016 / S0022-0000 (05) 80063-7 , les online )
2. * Xi Chen og Xiaotie Deng (2006) “Settling the complexity of two-player Nash equilibrium” i Proc. 47. symp. Grunnlaget for informatikk  : 261–271 s. ( DOI : 10.1109 / FOCS.2006.69 ).  .