Kekerasan UGC dari predikat

Latar belakang :

Dalam kertas UGC asli Subhash Khot ( PDF ), ia membuktikan kekerasan UG memutuskan apakah contoh CSP yang diberikan dengan kendala semua bentuk Tidak-semua-sama (a, b, c) pada alfabet ternary mengakui tugas yang memuaskan 1 - $\epsilon$ dari kendala atau apakah tidak ada tugas yang memuaskan $\frac{8}{9}+\epsilon$dari kendala, untuk kecil sewenang-wenang$\epsilon > 0$.

Saya ingin tahu apakah hasil ini telah digeneralisasi untuk setiap kombinasi $\ell$ kendala -ary untuk $\ell \ge 3$ dan domain variabel ukuran $k \ge 3$ mana $\ell \ne k \ne 3$ . Itu adalah,

Pertanyaan :

Adakah kekerasan yang diketahui dari hasil perkiraan untuk predikat $NAE(x_1, \dots, x_\ell)$ untuk $x_i \in GF(k)$ untuk $\ell, k \ge 3$ dan $\ell \ne k \ne 3$ ?

Saya terutama tertarik pada kombinasi nilai ; misalnya, predikat Tidak-sama-sama ( x 1 , ... , x k ) untuk x 1 ... , x k ∈ G F ( k ) .$\ell = k$$x_1, \dots, x_k$$x_1 \dots, x_k \in GF(k)$

Saya menyadari bahwa apa yang saya klaim di atas sebenarnya diketahui.

Untuk dan sewenang-wenang k ≥ 3 , ini ada dalam makalah FOCS 2002 milik Khot "Kekerasan mewarnai 3-seragam hypergraphs 3-warna" (makalah sebenarnya berbicara tentang umum k , meskipun judulnya hanya berbicara tentang kasus 3-warna) .$\ell = 3$$k \ge 3$$k$

Untuk dan k ≥ 2 , sebenarnya kekerasan yang lebih kuat diketahui. Bahkan jika ada sebenarnya tugas dari hanya dua nilai ke variabel yang memenuhi semua kendala NAE (dengan kata lain ℓ -uniform hipergraf dapat diwarnai menggunakan 2 warna tanpa hyperedge monokromatik), masih NP-keras untuk menemukan tugas dari ukuran domain k yang memenuhi setidaknya 1 - 1 / k ℓ - 1 + ε NAE kendala (untuk sewenang-wenang konstan ε > $\ell \ge 4$$k \ge 2$$\ell$$k$$1-1/k^{\ell-1}+\epsilon$$\epsilon > 0$). Ini mengikuti dengan mudah dari fakta bahwa hasil ketidaktepatan yang diketahui untuk hypergraph 2-coloring memberikan pernyataan kepadatan yang kuat dalam kasus kesehatan. Pernyataan formal muncul dalam makalah SODA 2011 saya dengan Ali Sinop "Kompleksitas menemukan set independen dalam derajat terikat (hiper) grafik angka kromatik rendah" (Lemma 2.3 dalam versi final SODA, dan Lemma 2.8 dalam versi yang lebih lama tersedia di ECCC http://eccc.hpi-web.de/report/2010/111/ ).

Saya mendapatkan halaman ini dari pencarian tentang NAE-3SAT.

Saya cukup yakin bahwa untuk masalah yang Anda tanyakan, harus NP-sulit untuk mengatakan apakah contoh memuaskan, atau jika paling banyak fraksi kendala dapat dipenuhi. Yaitu, hasil kekerasan yang ketat (cocok dengan apa yang hanya memilih tugas acak akan mencapai), untuk contoh yang memuaskan , dan tidak perlu untuk UGC.$1-1/k^{\ell-1}+\epsilon$

Untuk dan ℓ ≥ 4 , ini mengikuti dari faktor Hastad 7/8 + epsilon hasil yang tidak diperkirakan untuk pemisahan 4-set (yang kemudian dapat dikurangi menjadi pemisahan k-set untuk k > 4 ). Jika negasi tidak masalah, seseorang juga dapat menggunakan hasil kekerasannya yang ketat untuk Max ( ℓ - 1 ) -SAT.$k=2$$\ell \ge 4$$k > 4$$\ell-1$

Untuk , Khot membuktikan ini dalam makalah FOCS 2002 "Kekerasan mewarnai 3-seragam hypergraphs 3-warna." (Yaitu, ia menghapus asumsi UGC asli.)$k=\ell=3$

$\ell=3$$k\ge 3$$x_i+a,x_j+b,x_k$$a,b$

Untuk kasus umum, saya tidak tahu apakah ini telah ditulis di mana saja. Tetapi jika Anda benar-benar membutuhkannya, saya mungkin dapat menemukan sesuatu atau memeriksa klaim.

Prasad Raghavendra dalam STOC'08 Best Paper membuktikan, dengan asumsi Unique Games Conjecture, bahwa algoritma pemrograman semidefinite sederhana memberikan perkiraan terbaik untuk setiap masalah kepuasan kendala (termasuk NAE) dengan kendala jumlah variabel konstan masing-masing dan dengan alfabet konstan. Untuk benar-benar tahu apa faktor kekerasan untuk NAE, Anda perlu memahami seberapa baik algoritma sederhana untuk itu, yaitu, membuktikan celah integral untuk program. Saya tidak tahu apakah seseorang sudah melakukan itu untuk NAE secara umum atau tidak.