Est-il difficile de compter le nombre d'optima locaux pour un problème dans PLS?

Pour un problème de recherche locale polynomiale , on sait qu'au moins une solution (optimum local) doit exister. Cependant, de nombreuses autres solutions pourraient exister, est-il difficile de compter le nombre de solutions pour un problème PLS complet? Je suis particulièrement intéressé par le problème de décision: cette instance de problème PLS complet a-t-elle deux solutions ou plus?

La complexité dépend-elle du problème PLS complet que nous choisissons? Si c'est le cas, je serais particulièrement intéressé par le 2SAT pondéré (tel que défini dans [SY91] et [Rou10]). Je sais que compter le nombre de solutions satisfaisantes pour 2SAT est # P-complet, mais à première vue, il semble que les optima locaux de 2SAT pondérés et les solutions pour 2SAT n'aient pas grand-chose en commun.

Je sais aussi que pour le cousin PPS de PLS, [CS02] montre que compter le nombre d'équilibres de Nash est # P-difficile. Cela suggère que des problèmes PLS similaires, comme le comptage du nombre d'équilibres de stratégie pure dans les jeux de congestion, seraient également difficiles.

Références

[CS02] Conitzer, V. et Sandholm, T. (2002). Résultats de complexité sur les équilibres de Nash. IJCAI-03 . cs / 0205074 .

[Rou10] T. Roughgarden. (2010). Équilibres informatiques: une perspective de complexité informatique. Théorie économique , 42: 193-236.

[SY91] AA Schaeffer et M. Yannakakis. (1991). Problèmes de recherche locale simples et difficiles à résoudre. SIAM Journal on Computing , 20 (1): 56-87.

Je peux partiellement répondre à votre question: compter les optima locaux d'un problème de recherche PLS complet peut en effet être difficile.

Premièrement, comme Yoshio le fait remarquer, il existe un problème de recherche dans PLS dont le problème de comptage associé est # P-complet. ( Cependant, nous ne savons pas si est PLS complet.) Soit un problème PLS complet. Définissez ensuite qui, à l'entrée pour , demande un optimum local pour l'entrée par rapport à . Ce problème hérite de l'appartenance PLS de , hérite de l'exhaustivité PLS de et pour le problème de comptage hérite de l'exhaustivité # P de .$P_1$$P_1$$P_2$$P'$$(x, i)$$i \in \{1, 2\}$$x$$P_i$$P_1, P_2$$P_2$$P_1$

De même, on peut construire un problème PLS (artificiel) complet pour lequel il est NP-complet de décider s'il y a plus d'un optimum local. Comme dans l'argument précédent, on "agrafe ensemble" un problème PLS complet comme précédemment, avec un problème PLS qui, en entrée une formule booléenne , a plus d'un optimum local associé si siff est satisfaisable.$P_1$$P_2$$\psi$$\psi$

Ces types de constructions sont quelque peu insatisfaisants car nous essayons de construire un problème de recherche qui a deux propriétés de dureté, mais le domaine de "se divise" en deux morceaux, chacun pouvant ne posséder qu'une seule des deux propriétés. Ci-dessous, je vais montrer comment, étant donné un problème de recherche dans PLS dont le problème de comptage associé est # P-complet, et étant donné un problème PLS-complet , on peut définir un problème PLS qui est aussi difficile que de compter pour et recherchez de façon "instance par instance".$Q$$Q$$P_1$$P_2$$Q$$P_1$$P_2$

A savoir, nous montrerons telle sorte que la résolution du problème de comptage pour sur l'entrée réduit efficacement à la résolution du problème de comptage pour sur l'entrée , et le problème de recherche pour sur l'entrée réduit au problème de recherche pour sur l'entrée .$Q$$P_1$$x$$Q$$x$$P_2$$x$$Q$$x$

Pour simplifier la présentation, nous supposons que sont tels que sur toute entrée de longueur , l'espace candidat-solution associé à est sur les chaînes de bits de longueur pour certains (mais avec des structures de voisinage différentes pour ). Soit la fonction de fitness associée à .$P_1, P_2$$x$$n$$x$$y$$n^c$$c$$P_1, P_2$$F_i(x, y)$$P_i$

À l'entrée , l'espace de recherche pour est sur des tuples où chaque est dans , , et . Comme la fonction de fitness pour , nous définissons$x \in \{0, 1\}^n$$Q$$(y^1, y^2, z, b)$$y^i$$\{0, 1\}^{n^c}$$z \in \{0, 1\}^{n^c + 1}$$b \in \{0, 1\}$$F(x, (y^1, y^2, z, b))$$Q$

$F(x, (y^1, y^2, z, b)) := F_1(x, y^1) + F_2(x, y^2)$ si , $b = 1$

$F(x, (y^1, y^2, z, b)) := ||y^1|| + ||z|| + F_2(x, y^2)$ si .$b = 0$

(C'est le poids de Hamming ci-dessus.)

Pour la structure de voisinage de , nous connectons chaque tuple (avec ) à tous les tuples tels que$Q$$(x, (y^1, y^2, z, 1))$$b = 1$$(x, ((y')^1, (y')^2, z', 1))$

(A) est connecté à selon pour , ET$(x, y^i)$$(x, (y')^i)$$P_i$$i = 1, 2$

(B) diffèrent par au plus 1 coordonnée.$z, z'$

Pour les tuples avec , nous connectons à tous les tuples tel que$b = 0$$(x, (y^1, y^2, z, 0))$$(x, ((y')^1, (y')^2, z', 0))$

(A ') est connecté à selon , ET$(x, y^2)$$(x, (y')^2)$$P_2$

(B ') diffèrent par au plus 1 coordonnée, tout comme .$z, z'$$y^1, (y')^1$

(Notez que les tuples avec sont déconnectés de ceux avec )$b = 0$$b = 1$

Voilà la définition de . Les quartiers sont de taille polynomiale selon les besoins, donc est en PLS. $Q$$Q$

Affirmation: Les optima locaux pour la longueur entrée selon sont exactement les deux ensembles disjoints suivants:$n$$x$$Q$

(1) tous les tuples , où est un optimum local de$(x, (y^1, y^2, z,1))$$(x, y^i)$$P_i$$i = 1, 2$$z$$b = 1$

$(x, 1^{n^c}, y^2, 1^n, 0))$$(x, y^2)$$P_2$$z, y^1$$b = 0$

$Q$$(x, (y^1, y^2, z,b))$$Q$$x$$(x, y^2)$$P_2$$x$$P_2$

$N(x)$$x$$Q$$(2^{n^c + 1} N_1(x) + 1) \cdot N_2(x)$$N_i(x)$$x$$P_i$$N_2(x)$$[1, 2^{n^c}]$

$N_2(x) = N_2(x)$ mod mod mod .$2^{n^c + 1} = (2^{n^c + 1} N_1(x) + 1) \cdot N_2(x)$$2^{n^c + 1} = N(x)$$2^{n^c + 1}$

Nous pouvons donc obtenir étant donné . On peut alors aussi obtenir , par simple algèbre: . Comme est # P-complet à calculer, . Ainsi, il est # P-complet de compter les optima locaux pour (et compter pour réduit à compter pour sur la même instance). $N_2(x)$$N(x)$$N_1(x)$$N_1(x) = \left(\frac{N(x)}{N_2(x)} - 1\right)/2^{n^c + 1}$$N_1(x)$$N(x)$$Q$$P_1$$Q$

Je ne sais pas comment donner une telle réduction pour combiner la dureté PLS avec la dureté NP pour décider de l'unicité des optima locaux d'une manière "instance par instance".

Quant à savoir si chaque problème de recherche PLS complet génère un problème de comptage # P-complet, je ne le sais pas non plus. Il semble lié à la question de savoir si, pour chaque problème de décision NP-complet L et pour chaque vérificateur de polytemps pour , le problème de comptage des témoins associé est # P-complet. # La complétude P est valable dans tous les cas spécifiques que les gens ont envisagés, et dans certaines conditions raisonnablement douces, mais elle est ouverte en général. Voir cette discussion .$V(x, y)$$L$

$Q$$Q$

Considérez le problème de correspondance maximale dans les graphiques bipartites. La famille de solutions réalisables comprend toutes les correspondances, et la recherche locale est effectuée via la recherche de chemins d'augmentation. Le problème appartient à PLS puisqu'un chemin d'augmentation peut être trouvé en temps polynomial si une correspondance de courant n'est pas maximale, et la maximalité peut être vérifiée en temps polynomial. Tout optimum local est un maximum d'appariement (c'est-à-dire un optimum global). Cependant, il est difficile de calculer le nombre de correspondances maximales dans un graphe biparti.

Puisqu'un optimum local peut être trouvé en temps polynomial, il est peu probable que le problème soit complet en PLS. Donc, je crains que ce ne soit pas une réponse voulue (votre question se limite aux problèmes PLS complets). Cependant, je dois souligner que le comptage du nombre d'optima local peut être difficile même si un optimum local peut être trouvé efficacement.