Wie schwer ist es, die Anzahl der lokalen Optima für ein Problem in PLS zu zählen?

Für ein polynomielles lokales Suchproblem wissen wir, dass mindestens eine Lösung (lokales Optimum) existieren muss. Es könnten jedoch noch viele weitere Lösungen existieren. Wie schwierig ist es, die Anzahl der Lösungen für ein PLS-vollständiges Problem zu zählen? Das Entscheidungsproblem interessiert mich besonders : Hat die Instanz dieses PLS-vollständigen Problems zwei oder mehr Lösungen?

Hängt die Komplexität davon ab, welches PLS-vollständige Problem wir wählen? Wenn ja, dann würde mich besonders gewichtetes 2SAT interessieren (wie in [SY91] und [Rou10] definiert). Ich weiß, dass das Zählen der Anzahl zufriedenstellender Lösungen für 2SAT # P-vollständig ist, aber auf den ersten Blick scheinen lokale Optima von gewichtetem 2SAT und Lösungen für 2SAT nicht allzu viel gemeinsam zu haben.

Ich weiß auch, dass für PLSs Cousin PPAD [CS02] zeigt, dass das Zählen der Anzahl der Nash-Gleichgewichte # P-schwer ist. Dies deutet darauf hin, dass ähnliche PLS-Probleme wie das Zählen der Anzahl von Gleichgewichten mit reinen Strategien in Überlastungsspielen ebenfalls schwierig wären.

Verweise

[CS02] Conitzer, V. und Sandholm, T. (2002). Komplexitätsergebnisse über Nash-Gleichgewichte. IJCAI-03 . cs / 0205074 .

[Rou10] T. Roughgarden. (2010). Rechengleichgewichte: Eine Perspektive der Rechenkomplexität. Economic Theory , 42: 193 & ndash; 236.

[SY91] AA Schaeffer und M. Yannakakis. (1991). Einfache lokale Suchprobleme, die schwer zu lösen sind. SIAM Journal on Computing , 20 (1): 56-87.

Ich kann Ihre Frage teilweise beantworten: Das Zählen der lokalen Optima eines PLS-vollständigen Suchproblems kann in der Tat # P-schwer sein.

Erstens gibt es, wie Yoshio betont, ein Suchproblem in PLS, dessen zugehöriges Zählproblem # P-vollständig ist. (Wir wissen jedoch nicht, ob P 1 PLS-vollständig ist.) Sei P 2 ein PLS-vollständiges Problem. Definieren Sie dann P ', das bei Eingabe ( x , i ) für i ∈ { 1 , 2 } nach einem lokalen Optimum für Eingabe x in Bezug auf P i fragt . Dieses Problem erbt die PLS-Mitgliedschaft von P 1 , P $P_1$$P_1$$P_2$$P'$$(x, i)$$i \in \{1, 2\}$$x$$P_i$$P_1, P_2$, erbt die PLS-Vollständigkeit von und erbt für das Zählproblem die # P-Vollständigkeit von P 1 .$P_2$$P_1$

In ähnlicher Weise kann man ein (künstliches) PLS-vollständiges Problem konstruieren, für das es NP-vollständig ist, um zu entscheiden, ob es mehr als ein lokales Optimum gibt. Wie im vorherigen Argument "heftet" man ein PLS-vollständiges Problem wie zuvor zusammen, mit einem PLS-Problem P 2 , dem bei Eingabe einer Booleschen Formel ψ mehr als ein lokales Optimum zugeordnet ist, wenn ψ erfüllt werden kann.$P_1$$P_2$$\psi$$\psi$

Diese Art von Konstruktionen ist etwas unbefriedigend, weil wir versuchen, ein Suchproblem zu erstellen , das zwei Härteeigenschaften aufweist, aber die Domäne von Q in zwei Teile "aufteilt", von denen jede möglicherweise nur eine der beiden Eigenschaften aufweist. Im Folgenden werde ich zeigen, wie man bei einem Suchproblem P 1 in PLS, dessen zugehöriges Zählproblem # P-vollständig ist, und bei einem PLS-vollständigen Problem P 2 ein PLS-Problem Q definieren kann, das so schwierig ist, wie beide zählen P 1 und suchen Sie "Instanz für Instanz" nach P 2 .$Q$$Q$$P_1$$P_2$$Q$$P_1$$P_2$

Wir werden nämlich so zeigen , dass sich das effiziente Lösen des Zählproblems für P 1 bei Eingabe x auf das Lösen des Zählproblems für Q bei Eingabe x und das Suchproblem für P 2 bei Eingabe x auf das Suchproblem bei Q bei reduziert Eingabe x .$Q$$P_1$$x$$Q$$x$$P_2$$x$$Q$$x$

Zur Vereinfachung der Darstellung nehmen wir an so sind, dass auf jedem Eingang x der Länge n , der Kandidat-Lösungsraum mit zugeordnetem x über bitstrings ist y der Länge n c für einig c (aber mit verschiedenen Nachbarschaftsstrukturen für P 1 , P 2 ). Sei F i ( x , y ) die mit P i verbundene Fitnessfunktion .$P_1, P_2$$x$$n$$x$$y$$n^c$$c$$P_1, P_2$$F_i(x, y)$$P_i$

Bei der Eingabe liegt der Suchraum für Q über Tupeln ( y 1 , y 2 , z , b ), wobei sich jedes y i in { 0 , 1 } n c , z ∈ { 0 , 1 befindet } n c + 1 und b ∈ { 0 , 1 $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\}$. Als Fitnessfunktion für Q definieren wir$F(x, (y^1, y^2, z, b))$$Q$

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

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

(Das ist Hamming Gewicht oben.)

Für die Nachbarschaftsstruktur von verbinden wir jedes Tupel ( x , ( y 1 , y 2 , z , 1 ) ) (mit b = 1 ) mit allen Tupeln ( x , ( ( y ' ) 1 , ( y ' ) 2 , z ' , 1 ) ) so, dass$Q$$(x, (y^1, y^2, z, 1))$$b = 1$$(x, ((y')^1, (y')^2, z', 1))$

(A) ist gemäß P i für i = 1 , 2 UND mit ( x , ( y ' ) i$(x, y^i)$$(x, (y')^i)$$P_i$$i = 1, 2$

(B) unterscheiden sich in höchstens 1 Koordinate.$z, z'$

Für Tupel mit verbinden wir ( x , ( y 1 , y 2 , z , 0 ) ) mit allen Tupeln ( x , ( ( y ' ) 1 , ( y ' ) 2 , z ' , 0 ) ) wie z Das$b = 0$$(x, (y^1, y^2, z, 0))$$(x, ((y')^1, (y')^2, z', 0))$

(A ') ist gemäß P 2 UND mit ( x , ( y ' ) 2$(x, y^2)$$(x, (y')^2)$$P_2$

(B ') unterscheiden sich in höchstens 1 Koordinate, ebenso wie y 1 , ( y ' ) 1 .$z, z'$$y^1, (y')^1$

(Beachten Sie, dass Tupel mit von denen mit b = 1 getrennt werden .)$b = 0$$b = 1$

Das ist die Definition von . Die Nachbarschaften haben je nach Bedarf eine Polynomgröße, daher ist Q in PLS. $Q$$Q$

Behauptung: Die lokalen Optima für die Länge Eingabe x gemäß Q sind genau die folgenden zwei disjunkten Mengen:$n$$x$$Q$

(1) alle Tupel , wobei ( x , y i ) ein lokales Optimum von P i für jedes von i = 1 , 2 ist (und z willkürlich ist, und b = 1 ); und,$(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)$$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}$

$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$

Ich weiß nicht, wie ich eine solche Reduzierung für die Kombination der PLS-Härte mit der NP-Härte geben kann, um die Eindeutigkeit lokaler Optima "instanzweise" zu bestimmen.

$V(x, y)$$L$

$Q$$Q$

Betrachten Sie das Problem der maximalen Übereinstimmung in zweigeteilten Diagrammen. Die Familie der möglichen Lösungen besteht aus allen Übereinstimmungen, und die lokale Suche wird über das Auffinden von Erweiterungspfaden durchgeführt. Das Problem gehört zu PLS, da ein Erweiterungspfad in der Polynomzeit gefunden werden kann, wenn eine Stromanpassung nicht maximal ist, und die Maximalität in der Polynomzeit überprüft werden kann. Jedes lokale Optimum ist eine maximale Übereinstimmung (dh ein globales Optimum). Es ist jedoch # P-schwer, die Anzahl der maximalen Übereinstimmungen in einem zweigeteilten Diagramm zu berechnen.

Da ein lokales Optimum in der Polynomzeit gefunden werden kann, ist es unwahrscheinlich, dass das Problem PLS-vollständig ist. Ich fürchte, dies ist keine beabsichtigte Antwort (Ihre Frage beschränkt sich auf PLS-vollständige Probleme). Ich möchte jedoch darauf hinweisen, dass das Zählen der Anzahl lokaler Optima schwierig sein kann, obwohl ein lokales Optimum effizient gefunden werden kann.