Penjelasan murni teoretis-teoretis tentang reduksi dari Unique Label Cover ke Max-Cut

Saya sedang mempelajari Konjektur Game Unik dan pengurangan terkenal untuk Max-Cut dari Khot et al. Dari makalah mereka dan di tempat lain di internet, sebagian besar penulis menggunakan (apa yang bagi saya adalah) kesetaraan implisit antara pengurangan MAX-CUT dan membangun tes khusus untuk kode panjang. Karena ketidakjelasan saya tentang kesetaraan itu, saya berjuang untuk mengikuti alur pemikiran ini.

Tampaknya juga jelas dari paparan ini bahwa seseorang dapat menggambarkan pengurangan semata-mata dalam hal grafik, tetapi bahwa secara kebetulan atau preferensi tidak ada yang memilih untuk melakukannya dengan cara itu. Misalnya, dalam catatan kuliah O'Donnell ini ia mengisyaratkan bahwa tes kode panjang sesuai dengan definisi alami dari tepi pada grafik yang sedang dibangun, tetapi karena tidak dijabarkan bahwa aturan tampaknya tergantung pada pilihan potongan untuk mendefinisikan fungsi boolean yang sedang diuji, dan itu membuat saya agak bingung.

Jadi saya meminta seseorang untuk menjelaskan pengurangan "hanya" grafik-secara teoritis. Saya pikir ini akan membantu saya memahami kesetaraan antara dua sudut pandang.

Biarkan saya melihat apakah saya dapat mengklarifikasi ini, pada tingkat tinggi. Asumsikan turunan UG adalah grafik bipartit , bijections { π e } e ∈ E , di mana π e : Σ → Σ , dan | Σ | = m . Anda ingin membuat grafik H baru sehingga jika instance UG adalah 1 - δ memuaskan, maka H memiliki potongan besar, dan jika instance UG bahkan tidak δ -sangat memuaskan, maka$G = (V \cup W, E)$$\{\pi_e\}_{e \in E}$$\pi_e\colon \Sigma \to \Sigma$$|\Sigma| = m$$H$$1-\delta$$H$$\delta$ hanya memiliki potongan yang sangat kecil.$H$

Grafik berisi, untuk setiap simpul di W , awan 2 m poin, masing-masing dilabeli oleh beberapa x ∈ { - 1 , 1 } Σ . Tujuannya adalah bahwa Anda harus dapat menafsirkan kode panjang pengkodean dari label W sebagai potongan H . Ingat bahwa untuk mengkodekan beberapa σ ∈ Σ dengan kode panjang, Anda menggunakan fungsi boolean f : { - 1 $H$$W$$2^m$$x \in \{-1, 1\}^\Sigma$$W$$H$$\sigma \in \Sigma$$f\colon \{-1, 1\}^\Sigma \to \{-1, 1\}$; khususnya itu adalah fungsi diktator yang f ( x ) = 1 . Semua yang lain pergi ke T . Mari kita menghasilkan potongan S ∪ T (yaitu bi-partisi dari simpul) dari pengkodean kode panjang sebagai berikut. Jika w ∈ W memiliki label yang dikodekan oleh fungsi boolean f , pergi ke awan simpul dalam H yang sesuai dengan w , dan letakkan di S semua simpul di awan yang diberi label oleh beberapa$f(x) = x_\sigma$$S\cup T$$w \in W$$f$$H$$w$$S$$x$$f(x) = 1$$T$. Anda dapat melakukan mundur ini untuk menetapkan fungsi boolean untuk semua didasarkan pada potongan H .$w \in W$$H$

Agar pengurangan bekerja, Anda hanya perlu mengetahui dengan melihat nilai potongan $S\cup T$ apakah fungsi boolean yang terkait dengan pemotongan dekat dengan kode panjang pengkodean dari beberapa penugasan label ke yang memenuhi banyak kendala UG dari G . Jadi pertanyaannya adalah apa informasi yang kita dapatkan dari nilai dari potongan S ∪ T . Pertimbangkan dua simpul a dengan label x di cloud yang bersesuaian dengan w dan b dengan label y di cloud yang bersesuaian dengan w $W$$G$$S \cup T$$a$$x$$w$$b$$y$$w'$(dalam reduksi kita hanya melihat , w ′ di awan yang berbeda). Kami mengatakan bahwa cut dapat digunakan untuk fungsi boolean Turunkan f w dan f w ' . Sekarang jika ada tepi ( a , b ) di H , maka ( a , b ) dipotong jika dan hanya jika f w ( x ) ≠ f w ' ( y $w$$w'$$f_w$$f_{w'}$$(a,b)$$H$$(a, b)$$f_w(x) \neq f_{w'}(y)$. Oleh karena itu, hanya menggunakan nilai cut untuk mengetahui apakah fungsi boolean yang diinduksi adalah "baik" sama dengan memiliki tes itu, mengingat fungsi boolean f w ′ ( y ) .$\{f_w\}_{w \in W}$, hanya menanyakan fraksi apa dari beberapa daftar pasangan tertentu kita memiliki f w ( x ) $((w, x), (w', y))$$f_w(x) \neq f_{w'}(y)$

Dengan kata lain, setiap kali Ryan mengatakan dalam catatan "tes jika ", apa yang sebenarnya ia maksudkan adalah "dalam H , tambahkan tepi antara titik di awan dari w yang dilabeli oleh x dan titik di awan w ′ dilabeli oleh y ". Yaitu untuk setiap v ∈ V , setiap dua tetangganya w , w ′ , dan setiap x , y ∈ { - 1 , 1 $f_w(x) \neq f_{w'}(y)$$H$$w$$x$$w'$$y$$v\in V$$w, w'$ , termasuk tepi antara simpul di awan w yang diberi label$x,y \in \{-1, 1\}^n$$w$ dan simpul di awan w ′ dilabeli oleh y ∘ π v , w ′ , dan tetapkan bobot tepi ( ( 1 - ρ ) / 2 ) d ( ( 1 + ρ ) / 2 ) $x\circ \pi_{v,w}$$w'$$y \circ \pi_{v,w'}$ manadadalah jarak Hamming antara$(({1-\rho})/{2})^d(({1+\rho})/{2})^{n-d}$$d$$x$dan . Dengan cara ini nilai potongan dibagi dengan berat tepi total persis sama dengan probabilitas keberhasilan tes.$y$