PPAD capture-t-il vraiment la notion de trouver un autre sommet déséquilibré?

13

La complexité classe PPAD a été inventé par Christos Papadimitriou dans son 1994 fondateur du papier . La classe est conçue pour capturer la complexité des problèmes de recherche où l'existence d'une solution est garantie par "Argument de parité dans les graphes dirigés": s'il y a un sommet déséquilibré dans un graphe orienté alors il doit en exister un autre. Mais généralement, la classe est formellement définie en termes de problème ( ), où l'argument est appliqué uniquement aux graphiques avec des degrés d'entrée et de sortie . Ma question est: pourquoi ces notions sont-elles équivalentes?ANOTHER END OF THE LINEAEOL1

Jusqu'à présent, c'est un double de cette question . Maintenant, je veux formaliser le problème et clarifier pourquoi je ne suis pas satisfait de la réponse.

Problème de recherche ( ): on nous donne deux circuits de taille polynomiale et qui obtiennent et renvoient une liste polynomiale de d'autres éléments dans . Ces circuits définissent un graphe orienté où et . Le problème de recherche est le suivant: étant donné , et tels que , trouver un autre sommet avec la même propriété.ANOTHER UNBALANCED VERTEXAUVSPx{0,1}n{0,1}nG=(V,E)V={0,1}n(x,y)E(yS(x)xP(y))SPzVindegree(z)outdegree(z)

Problème de recherche : le même, mais et renvoient une liste vide ou un élément.AEOLSP

La notion de réductibilité (corrigée selon la suggestion de Ricky): le problème de recherche total est réductible au problème de recherche total via les fonctions polynomiales et si est une solution à dans le problème implique est une solution de dans problème . ABfgyf(x)Bg(x,y)xA

Question formelle : pourquoi réductible à ? Ou devrions-nous utiliser une autre notion de réductibilité?AUVAEOL

Christos Papadimitriou prouve un théorème analogue sur le PPA (Théorème 1, page 505) mais l'argument ne semble pas fonctionner pour PPAD . La raison en est qu'un sommet de degré d'équilibre sera transformé en sommets de degré d'équilibre . Ensuite, l'algorithme pour peut obtenir l'un de ces sommets et en retourner un autre. Cela ne donnerait pas de nouveau sommet pour .k ± 1 A E O L A U V±kk±1AEOLAUV

Les choses empirent car dans il y a toujours un nombre pair de sommets non équilibrés mais dans il peut y en avoir un nombre impair. C'est pourquoi on ne peut pas construire une bijection entre ces deux ensembles et ne peut pas toujours être égal à . Si alors nous obtenons une méthode pour résoudre en temps polynomial au moins pour certains cas. Si ne dépend pas de et pour alors peut être renvoyé comme réponse pour . Cela ne donnerait pas de solution pourA U V g f - 1 g ( x , f ( x ) ) x A U V g x g ( y 1 ) = g ( y 2 ) y 1y 2 y 2 y 1 A U VAEOLAUVgf1g(x,f(x))xAUVgxg(y1)=g(y2)y1y2y2y1AUV .

Dernière question : les obstacles énumérés ci-dessus peuvent-ils être surmontés d'une manière ou d'une autre? Peut-on employer une éventuelle dépendance de à ?xgx

Daniil Musatov
la source
2
"pourquoi ces notions sont-elles équivalentes?" Pour les raisons données dans la preuve du théorème 1 page 505 de Christos Papadimitriou. (Sinon, quel est, selon vous, un argument de parité pour la totalité des AUV?) Votre définition de la réductibilité semble trop forte - Par exemple, selon votre définition, étendre l'ensemble de solutions peut rendre un problème de recherche total strictement plus difficile.
2
+1 et -1 ont la même parité. (Cette parité est "impaire".) La bonne a "implique " au lieu de "ssi ". g (g(x,y)g(y)
2
Maintenant, ce que nous ne disposons que, je vais l' appeler UnbalancedInOtherDirectionVertex, ce problème se réduit à PPADS , car on ne peut retourner les bords si nécessaire pour rendre le sommet donné une plus grande à degrés qu'en degrés, puis la totale -degree-1 sommets dans lesquels le sommet donné est transformé seront tous des sources plutôt que des puits. Je ne vois aucune manière similaire de passer de votre problème à AEOL. k
1
Au moins, la réduction montre que l'AUV est équivalent à son cas où tous les sommets ont un degré et un degré extérieur au plus 1, sauf éventuellement pour le sommet z donné, qui a un degré 0, mais peut avoir un grand degré extérieur.
Emil Jeřábek le
2
Je viens d'entendre Frédéric Meunier qu'il a également observé ce problème il y a cinq ans et Papadimitriou a accepté.
domotorp

Réponses:

4

C'est une question intéressante, et je ne peux donner qu'une réponse partielle.

Il est facile de voir que la construction de la p. 505 du papier de Papadimitriou montre l'équivalence de l' AUV avec son cas spécial

BEAUCOUP D'EXTRÉMITÉS DE LA LIGNE (MEOL): Étant donné un graphe orienté avec en degrés et en degrés au plus (représenté par des circuits comme ci-dessus), et un ensemble non vide de sources de , trouver un puits ou une source .1 X G v XG1XGvX

D'une part, j'ai du mal à imaginer une transformation de tels graphes qui pourrait réduire un plus grand nombre de sources à un.

Cependant, d'autre part, MEOL appartient à toutes les classes couramment étudiées contenant du PPAD, à l' exception peut-être du PPAD lui-même:

Tout d'abord, évidemment,

MEOL est en PPADS .

Je vais esquisser ci-dessous un argument

MEOL est en PPA

par réduction au problème standard PPA- complet (la version non dirigée d' AEOL ). Supposons que l'on nous donne et comme dans la définition de MEOL.XG=(V,E)X

Siest étrange, nous pouvons simplement rendre le graphique non orienté, inclure une correspondance sur tous les sommets sauf un de (comme dans l'argument de la p. 505), et transmettre le résultat avec la source restante de à l' oracle PPA .X X|X|XX

En général, soit, et est la plus grande puissance de qui divise . Nous définissons un nouveau graphe dont les sommets sont -Element sous - ensembles de . Si sont de tels ensembles, nous mettons l'arête dans si nous pouvons énumérer les ensembles comme , de telle sorte que pour chaque .s=|X|2k2sG=(V,E)2kVA,BV(A,B)EA={a0,,a2k1}( a i , b i )Ei< 2 kB={b0,,b2k1}(ai,bi)Ei<2k

Clairement, est un graphe orienté avec en degrés et en degrés au plus . Un est une source (puits) ssi elle contient une source (évier, resp.) De . (Autrement dit, s'il contient les deux, c'est un sommet isolé.) Donc, un tel sommet mènerait à une solution de l' instance MEOL , à moins que ne soit une "source connue": c'est-à-dire . Nous avons l'intention de rendre le graphique non orienté et de le manipuler de sorte que le nombre de sources connues soit réduit à en incluant une correspondance sur les autres. 1 A V G A A X 1G1AVGAAX1

Donc, si est une source connue, soit, ce qui satisfait . Si, Alors simplement . Le nombre de ces ensembles est . Rappelons que la multiplicité d'un premier dans est égale au nombre de portées dans l'addition effectué en base . Par le choix de , il s'ensuit que est impair. De plus, il existe des bijections en temps polynomial entre et des sous-ensembles d'éléments det = | A X | 0 < t 2 k t = 2 k = | A | A XAt=|AX|0<t2kt=2k=|A|AX(s2k)p(ab)b+(ab)=apk(s2k)[0,(ab))b[0,a). En utilisant cela, nous pouvons définir une correspondance polynomiale dans le temps sur tous les sous-ensembles d'éléments . Nous l'incluons dans le graphique, ce qui réduit le nombre de sources connues avec à .2kXt=2k1

Pour , la formule de comptage de report montre que est pair. Encore une fois, nous pouvons trouver une correspondance explicite sur sous - ensembles -Element de . Nous l'étendons aux sources connues avec en appliquant l'appariement à , et en laissant fixe.0<t<2k tXA| AX| =tAXAX(st)tXA|AX|=tAXAX

De cette façon, nous produisons un graphe non orienté avec un sommet de feuille connu. Nous demandons à l' oracle PPA une autre feuille, et par construction, nous pouvons en extraire une réponse pour l' instance MEOL .


Comme brièvement mentionné par Papadimitriou, nous pouvons généraliser PPA aux classes PPA - pour tout premier . Un exemple de problème PPA - complet estp pppp

AUV - : Étant donné un graphe orienté et un sommet dont le degré d'équilibre est , trouvez un autre tel sommet.GpG0(modp)

(Voir cette réponse pour l'équivalence de AUV - avec la définition de Papadimitriou de PPA - .)pp

PPA - est juste PPA . Les classes PPA - sont supposées incomparables par paire et incomparables avec PPADS . Ils incluent tous PPAD .2p

n'avait rien de particulièrement spécial dans l'argument que j'ai décrit ci-dessus, et il peut être facilement modifié pour donnerp=2

MEOL est en PPA - pour chaque nombre premier .pp

Emil Jeřábek
la source
J'aime beaucoup la réponse et j'ai décidé de l'accepter (bien sûr, des réponses plus complètes sont toujours les bienvenues). Je pense seulement que la classe représentée par AUV - devrait s'appeler PPAD - . Papadimitriou écrit sur les graphes bipartites non orientés et uniquement sur les degrés, pas sur les soldes. pp
Daniil Musatov
3
Les classes sont des généralisations de PPA, pas de PPAD, pour . Papadimitriou donne un problème complet différent de l'AUV- (notez que ses graphiques sont bipartis), mais il est équivalent à ma définition. L'ensemble du schéma de dénomination est terriblement déroutant; l'utilisation de graphes dirigés contre non orientés pour une classe particulière n'est qu'un accident, de nombreuses classes ont des problèmes complets concernant les graphes orientés et non orientés (comme dans le cas de PPA- ). De plus, malgré leurs noms, la plupart des classes ne sont pas basées sur des arguments de parité, mais sur d'autres principes de comptage. Seul le PPA concerne la parité. p=2pp
Emil Jeřábek
Merci, j'ai compris. C'est en effet la même classe. J'ai entendu une spéculation que Papadimitriou a choisi le nom PPAD parce qu'il ressemble à son propre nom de famille.
Daniil Musatov
Avez-vous une référence pour PPAD dans PPA-p?
domotorp
1
Pas explicite, mais par exemple, le problème définissant PPAD-complete est littéralement un cas spécial d'AUV- . p
Emil Jeřábek