PPAD (complexité)

Un article de Wikipédia, l'encyclopédie libre.
Ceci est une version archivée de cette page, en date du 26 janvier 2019 à 12:17 et modifiée en dernier par Fschwarzentruber (discuter | contributions). Elle peut contenir des erreurs, des inexactitudes ou des contenus vandalisés non présents dans la version actuelle.

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].

Définition

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Références

  1. ↑ 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)
  2. ↑ * 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    .
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=PPAD_(complexité)&oldid=156173318 ».