Seberapa sulit untuk menghitung jumlah optima lokal untuk masalah dalam PLS?

Untuk masalah pencarian lokal polinomial , kita tahu bahwa setidaknya ada satu solusi (lokal optimal) harus ada. Namun, banyak lagi solusi yang bisa ada, seberapa sulitkah menghitung jumlah solusi untuk masalah lengkap PLS? Saya terutama tertarik pada masalah keputusan: apakah contoh masalah PLS-lengkap ini memiliki dua solusi atau lebih?

Apakah kompleksitasnya tergantung pada masalah PLS-lengkap yang kita pilih? Jika demikian maka saya akan sangat tertarik pada 2SAT berbobot (sebagaimana didefinisikan dalam [SY91] dan [Rou10]). Saya tahu bahwa menghitung jumlah solusi yang memuaskan untuk 2SAT adalah # P-complete, tetapi pada pandangan pertama sepertinya optima lokal dari 2SAT berbobot dan solusi untuk 2SAT tidak memiliki banyak kesamaan.

Saya juga tahu bahwa untuk sepupu PLS, PPAD, [CS02] menunjukkan bahwa menghitung jumlah Nash equilibria adalah # P-hard. Ini menunjukkan bahwa masalah PLS yang serupa seperti menghitung jumlah kesetimbangan strategi murni dalam permainan kemacetan, juga akan sulit.

Referensi

[CS02] Conitzer, V., dan Sandholm, T. (2002). Hasil kompleksitas tentang Nash equilibria. IJCAI-03 . cs / 0205074 .

[Rou10] T. Roughgarden. (2010). Computing equilibria: Perspektif kompleksitas komputasi. Teori Ekonomi , 42: 193-236.

[SY91] AA Schaeffer dan M. Yannakakis. (1991). Masalah pencarian lokal sederhana yang sulit dipecahkan. Jurnal SIAM tentang Komputer , 20 (1): 56-87.

Saya dapat sebagian menjawab pertanyaan Anda: menghitung optima lokal dari masalah pencarian lengkap-PLS memang bisa menjadi # P-hard.

Pertama, seperti yang ditunjukkan Yoshio, ada masalah pencarian dalam PLS yang masalah penghitungannya terkait # P-selesai. (Namun, kami tidak tahu apakah P 1 selesai-PLS.) Biarkan P 2 menjadi masalah lengkap-PLS. Kemudian tentukan P ′ yang, pada input ( x , i ) untuk i ∈ { 1 , 2 } , meminta optimum lokal untuk input x sehubungan dengan P i . Masalah ini mewarisi keanggotaan PLS dari P 1 , P $P_1$$P_1$$P_2$$P'$$(x, i)$$i \in \{1, 2\}$$x$$P_i$$P_1, P_2$, mewarisi kelengkapan PLS dari , dan untuk masalah penghitungan mewarisi # P-kelengkapan dari P 1 .$P_2$$P_1$

Demikian pula, seseorang dapat membangun masalah (lengkap) PLS-lengkap yang NP-lengkap untuk memutuskan apakah ada lebih dari satu lokal optimal. Seperti pada argumen sebelumnya, satu "menjepit bersama-sama" masalah PLS-lengkap seperti sebelumnya, dengan masalah PLS P 2 yang, pada input rumus Boolean ψ , memiliki lebih dari satu optimum lokal terkait jika ψ memuaskan.$P_1$$P_2$$\psi$$\psi$

Konstruksi semacam ini agak tidak memuaskan karena kami mencoba membangun masalah pencarian yang memiliki dua sifat kekerasan, tetapi domain Q "terbagi" menjadi dua bagian, yang masing-masing mungkin hanya memiliki satu dari dua properti. Di bawah ini saya akan menunjukkan bagaimana, mengingat masalah pencarian P 1 dalam PLS yang terkait masalah penghitungannya adalah # P-complete, dan diberi masalah PLS-complete P 2 , orang dapat mendefinisikan masalah PLS Q yang sama sulitnya dengan keduanya menghitung untuk P 1 dan cari P 2 dengan cara "instance-by-instance".$Q$$Q$$P_1$$P_2$$Q$$P_1$$P_2$

Yaitu, kami akan menunjukkan sedemikian rupa sehingga menyelesaikan masalah penghitungan untuk P 1 pada input x secara efisien mengurangi untuk memecahkan masalah penghitungan untuk Q pada input x , dan masalah pencarian untuk P 2 pada input x mengurangi ke masalah pencarian untuk Q pada input x .$Q$$P_1$$x$$Q$$x$$P_2$$x$$Q$$x$

Untuk kesederhanaan presentasi, kita asumsikan sedemikian rupa sehingga pada setiap input x panjang n , ruang solusi-kandidat yang terkait dengan x melebihi bitstring y dengan panjang n c untuk beberapa c (tetapi dengan struktur lingkungan yang berbeda untuk P 1 , P 2 ). Biarkan F i ( x , y ) menjadi fungsi kebugaran yang terkait dengan P i .$P_1, P_2$$x$$n$$x$$y$$n^c$$c$$P_1, P_2$$F_i(x, y)$$P_i$

Pada input , ruang pencarian untuk Q melebihi tupel ( y 1 , y 2 , z , b ) di mana setiap y i berada di { 0 , 1 } n c , z ∈ { 0 , 1 } n c + 1 , dan 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\}$. Sebagai fungsi kebugaran untuk Q , kami mendefinisikan$F(x, (y^1, y^2, z, b))$$Q$

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

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

(Itu berat Hamming di atas.)

Untuk struktur lingkungan , kami menghubungkan setiap tupel ( x , ( y 1 , y 2 , z , 1 ) ) (dengan b = 1 ) ke semua tupel ( x , ( ( y ′ ) 1 , ( y ′ ) 2 , z ′ , 1 ) ) sedemikian rupa$Q$$(x, (y^1, y^2, z, 1))$$b = 1$$(x, ((y')^1, (y')^2, z', 1))$

(A) terhubung ke ( x , ( y ′ ) i ) menurut P i untuk i = 1 , 2 , DAN$(x, y^i)$$(x, (y')^i)$$P_i$$i = 1, 2$

(B) berbeda paling banyak dalam 1 koordinat.$z, z'$

Untuk tupel dengan , kami menghubungkan ( x , ( y 1 , y 2 , z , 0 ) ) ke semua tupel ( x , ( ( y ′ ) 1 , ( y ′ ) 1 , ( y ′ ) 2 , z ′ , 0 ) ) seperti bahwa$b = 0$$(x, (y^1, y^2, z, 0))$$(x, ((y')^1, (y')^2, z', 0))$

(A ') terhubung ke ( x , ( y ′ ) 2 ) menurut P 2 , DAN$(x, y^2)$$(x, (y')^2)$$P_2$

(B ') berbeda paling banyak dalam 1 koordinat, seperti halnya y 1 , ( y ′ ) 1 .$z, z'$$y^1, (y')^1$

(Catatan, tupel dengan terputus dari yang dengan b = 1. )$b = 0$$b = 1$

Itulah definisi . Lingkungannya berukuran polinom seperti yang diperlukan, jadi Q ada di PLS. $Q$$Q$

Klaim: Optima lokal untuk panjang- input x menurut Q adalah persis dua set terputus-putus berikut:$n$$x$$Q$

(1) semua tupel , di mana ( x , y i ) adalah optimum lokal P i untuk masing-masing i = 1 , 2 (dan z adalah arbitrer, dan b = 1 ); dan,$(x, (y^1, y^2, z,1))$$(x, y^i)$$P_i$$i = 1, 2$$z$$b = 1$

(2) semua tupel , di mana ( x , y 2 ) adalah optimum lokal dari P 2 , dan di mana z , y 1 keduanya semua-1, dan b = 0 .$(x, 1^{n^c}, y^2, 1^n, 0))$$(x, y^2)$$P_2$$z, y^1$$b = 0$

Jika Anda setuju, maka PLS-kekerasan segera, karena setiap optimum lokal ( x , ( y 1 , y 2 , z , b ) ) dari Q untuk input x memberikan optimum lokal ( x , y 2 ) dari P 2 (untuk input x yang sama ), dan P 2 adalah PLS-hard.$Q$$(x, (y^1, y^2, z,b))$$Q$$x$$(x, y^2)$$P_2$$x$$P_2$

Juga, dari Klaim kami bahwa jumlah dari optima lokal untuk x di bawah Q sama dengan ( 2 n c + 1 N 1 ( x ) + 1 ) ⋅ N 2 ( x ) , di mana N i ( x ) adalah jumlah optima lokal untuk x di bawah P i . Sekarang N 2 ( x ) berada dalam kisaran [ $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)$ , jadi sudah$[1, 2^{n^c}]$

mod 2 n c + 1 = ( 2 n c + 1 N 1 ( x ) + 1 ) ⋅ N 2 ( x ) mod 2 n c + 1 = N ( x ) mod 2 n c + 1 .$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}$

Jadi kita bisa mendapatkan diberikan N ( x ) . Maka kita juga bisa mendapatkan N 1 ( x ) , dengan aljabar sederhana: N 1 ( x ) = ( N ( x $N_2(x)$$N(x)$$N_1(x)$. KarenaN1(x)adalah # P-complete untuk menghitung, demikian jugaN(x). Jadi ini # P-selesai untuk menghitung optima lokal untukQ(dan menghitung untukP1mengurangi untuk menghitung untukQpada contoh yang sama). $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$

Saya tidak tahu bagaimana memberikan pengurangan untuk menggabungkan kekerasan PLS dengan kekerasan NP untuk memutuskan keunikan optima lokal dengan cara "contoh-oleh-contoh".

Mengenai apakah setiap masalah pencarian PLS-lengkap menghasilkan masalah penghitungan # P-complete, saya juga tidak tahu. Ini tampaknya terkait dengan pertanyaan apakah, untuk setiap NP-lengkap masalah keputusan L dan setiap polytime verifier untuk L , yang terkait masalah saksi-penghitungan adalah # P-lengkap. # Kelengkapan P berlaku dalam semua kasus tertentu yang orang pertimbangkan, dan dalam kondisi yang cukup ringan, tetapi terbuka secara umum. Lihat diskusi ini .$V(x, y)$$L$

Untuk masalah khusus, yang lebih alami, dikenal sebagai penyelesaian-PLS, orang mungkin dapat membangun # -pelengkapan untuk menghitung optima lokal dengan memberikan pengurangan-PLS dari say Matching to Q yang memiliki beberapa sifat khusus yang pantas untuk dihitung. Mungkin teknik yang ada sudah cukup; Saya belum mencoba memastikan.$Q$$Q$

Pertimbangkan masalah pencocokan maksimum dalam grafik bipartit. Keluarga solusi yang layak terdiri dari semua pencocokan, dan pencarian lokal dilakukan melalui pencarian jalur tambahan. Masalahnya milik PLS karena jalur augmentasi dapat ditemukan dalam waktu polinomial jika pencocokan saat ini tidak maksimal, dan maksimalitas dapat diperiksa dalam waktu polinomial. Setiap lokal optimal adalah pencocokan maksimum (yaitu global optimum). Namun, # P-sulit untuk menghitung jumlah pencocokan maksimum dalam grafik bipartit.

Karena optimum lokal dapat ditemukan dalam waktu polinomial, masalahnya tidak mungkin lengkap dengan PLS. Jadi, saya khawatir ini bukan jawaban yang dimaksudkan (pertanyaan Anda membatasi masalah lengkap PLS). Namun, saya harus menunjukkan bahwa menghitung jumlah optima lokal bisa sulit walaupun satu lokal optimal dapat ditemukan secara efisien.