PPA (complexité)
En informatique théorique, plus précisément en théorie de la complexité computationnelle, PPA est une classe de complexité, signifiant "Polynomial Parity Argument" (sur un graphe). Introduit par Christos Papadimitriou en 1994 [1] (page 528), PPA est une sous-classe de TFNP. PPA est une classe de problèmes de recherche dont on peut montrer qu'ils sont totaux par une application du lemme de la poignée de main : tout graphe non orienté qui a un sommet de degré impair doit avoir un autre sommet de degré impair . Cela signifie que si on nous donne un graphe et un sommet de degré impair, et qu'on nous demande de trouver un autre sommet de degré impair, alors nous recherchons quelque chose dont l'existence est garantie (nous avons donc un problème de recherche total).
Définition modifier
La classe PPA est défini comme suit. Supposons que nous ayons un graphe dont les sommets sont des mots de bits, et le graphe est représenté par un circuit de taille polynomiale qui prend un sommet en entrée et sort ses voisins (Remarquez que cela nous permet de représenter un graphique de taille exponentielle sur lequel nous pouvons effectuer efficacement une exploration locale). Supposons de plus qu'un sommet spécifique (disons le vecteur entièrement nul) ait un nombre impair de voisins. Nous devons trouver un autre sommet de degré impair. Ce problème est dans NP - étant donnée une solution, il peut être vérifié à l'aide d'un circuit que la solution est correcte. Un problème de calcul de fonction appartient à PPA s'il admet une réduction en temps polynomial à ce problème de recherche de graphe. Un problème est complet pour la classe PPA si de plus, ce problème de recherche de graphe est réductible à ce problème.
Liens avec d'autres classes modifier
La classe PPAD est définie de la même manière que PPA, sauf que PPAD est défini sur des graphes orientés. PPAD est une sous-classe de PPA. En effet, le problème correspondant qui définit PPAD, connu sous le nom de END OF THE LINE, peut être réduit à la recherche ci-dessus d'un sommet supplémentaire de degré impair (essentiellement, simplement en ignorant les directions des arêtes dans END OF THE LINE).
Exemples modifier
- Il existe une version non orientée du lemme de Sperner connue qui est PPA-complète[2].
- Le problème de réduction de moitié par consensus est connu pour être complet pour PPA[3].
- Le problème de la recherche d'un deuxième cycle hamiltonien sur un graphe 3-régulier fait partie de PPA, mais n'est pas connu pour être complet pour PPA.
- Il existe une réduction aléatoire en temps polynomial du problème de la factorisation entière aux problèmes complets pour PPA[4].
Références modifier
- 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 [archive du ], consulté le )
- Michelangelo Grigni, « A Sperner Lemma Complete for PPA », Information Processing Letters, vol. 77, nos 5–6, , p. 255–259 (DOI 10.1016/S0020-0190(00)00152-6, CiteSeerx 10.1.1.63.9463)
- A. Filos-Ratsikas et P.W. Goldberg « Consensus-Halving is PPA-Complete » () (DOI 10.1145/3188745.3188880, arXiv 1711.04503)
— « (ibid.) », dans Proc. of 50th Symposium on Theory of Computing, p. 51–64 - E. Jeřábek, « Integer Factoring and Modular Square Roots », Journal of Computer and System Sciences, vol. 82, no 2, , p. 380–394 (DOI 10.1016/j.jcss.2015.08.001, arXiv 1207.5220)
