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

11

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.

Artem Kaznatcheev
quelle

Antworten:

7

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 2P1P1P2P(x,i)i{1,2}xPiP1,P2, erbt die PLS-Vollständigkeit von und erbt für das Zählproblem die # P-Vollständigkeit von P 1 .P2P1

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.P1P2ψψ

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

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

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 .P1,P2xnxynccP1,P2Fi(x,y)Pi

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{0,1}nQ(y1,y2,z,b)yi{0,1}ncz{0,1}nc+1b{0,1}. Als Fitnessfunktion für Q definieren wirF(x,(y1,y2,z,b))Q

wenn b = 1 , F(x,(y1,y2,z,b)):=F1(x,y1)+F2(x,y2)b=1

wenn b = 0 .F(x,(y1,y2,z,b)):=||y1||+||z||+F2(x,y2)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, dassQ(x,(y1,y2,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 ) verbunden(x,yi)(x,(y)i)Pii=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 Dasb=0(x,(y1,y2,z,0))(x,((y)1,(y)2,z,0))

(A ') ist gemäß P 2 UND mit ( x , ( y ' ) 2 ) verbunden(x,y2)(x,(y)2)P2

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

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

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

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

(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,(y1,y2,z,1))(x,yi)Pii=1,2zb=1

(x,1nc,y2,1n,0))(x,y2)P2z,y1b=0

Q(x,(y1,y2,z,b))Qx(x,y2)P2xP2

N(x)xQ(2nc+1N1(x)+1)N2(x)Ni(x)xPiN2(x)[1,2nc]

N2(x)=N2(x)2nc+1=(2nc+1N1(x)+1)N2(x)2nc+1=N(x)2nc+1

N2(x)N(x)N1(x)N1(x)=(N(x)N2(x)1)/2nc+1N1(x)N(x)QP1Q


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

QQ

Andy Drucker
quelle
Als du, Andy! Das ist sehr nützlich. Ich muss es noch ein paar Mal durchlesen, um sicherzugehen, dass ich alles verfolge.
Artem Kaznatcheev
7

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.

Yoshio Okamoto
quelle
Vielen Dank! Dies ist ein guter allgemeiner Punkt, um über die # P-Härte im Allgemeinen Bescheid zu wissen (und warum ich 2SAT erwähnt habe). Ich werde die Frage offen halten, in der Hoffnung, einige Antworten auf PLS-vollständige Probleme zu erhalten, und ich werde mehr Wert darauf legen, eine einzelne Lösung von zwei oder mehr vorhandenen Lösungen zu unterscheiden (das ist der Fall, an dem ich eigentlich am meisten interessiert bin).
Artem Kaznatcheev
1
Da die Eindeutigkeit einer maximalen Übereinstimmung effizient überprüft werden kann, ist meine Antwort für die Frage, die Sie am meisten interessiert, nicht zufriedenstellend. Vielen Dank.
Yoshio Okamoto