Kesenjangan sulit dalam masalah kepuasan kendala maksimal?

12

Formulasi setara PCP teorema adalah: Untuk Max 3-SAT itu adalah -Hard untuk membedakan antara formula satisfiable dan formula mana paling r -fraction klausul yang satisfiable (untuk beberapa r < 1 ).NPrr<1

Apakah ada teorema dikotomi diketahui yang mengklasifikasikan semua CSP Max berdasarkan apakah ada celah yang sulit atau tidak?

Sunting 16 Des 2010 : MAX CSP dengan hard gap berarti bahwa masalahnya memiliki faktor tak-terduga optimal. Misalnya, 3SAT memiliki kesenjangan keras di lokasi satu karena merupakan polinomial waktu approximable untuk faktor tetapi N P -Hard untuk mendapatkan faktor pendekatan 7 / 8 + ε bahkan ketika semua klausul yang satisfiable.7/8NP7/8+ϵ

cc.complexity-theory pcp csp Mohammad Al-Turkistany
sumber

Jawaban:

18

Prasad Raghavendra dalam makalah terbaik STOC'08 membuktikan dugaan dikotomi untuk mendekati Max-CSP dengan asumsi Pertandingan Game Unik. Ini bukan bagaimana dia mempresentasikannya pada awalnya, tetapi dia memang memberikan ceramah yang menyajikan hal-hal seperti ini beberapa tahun kemudian, misalnya, di IAS, di mana video itu direkam: http://www.math.ias.edu/seminars/abstract ? acara = 36669

Perbedaan dari menunjukkan kekerasan SNP adalah bahwa di sini kita berbicara tentang hasil optimal secara kuantitatif.

Dana Moshkovitz
sumber
3
apa arti 'optimal secara kuantitatif'?
Suresh Venkat
3
faktor kekerasan yang cocok dengan algoritma aproksimasi paling terkenal
Dana Moshkovitz
6

Teorema 5.14 dari Khanna, Sudan, Trevisan dan Williamson [KSTW01] memberikan teorema dikotomi untuk versi kesenjangan dengan kelengkapan sempurna untuk masalah MaxCSP boolean.

[KSTW01] Sanjeev Khanna, Madhu Sudan, Luca Trevisan dan David P. Williamson. Perkiraan masalah kepuasan kendala. Jurnal SIAM tentang Komputer , 30 (6): 1863–1920, 2001. http://dx.doi.org/10.1137/S0097539799349948

Tsuyoshi Ito
sumber
Kertas yang menarik. Bagaimana teorema dikotomi ini terkait dengan hasil Raghavendra dalam jawaban Dana ?.
Mohammad Al-Turkistany
Saya pikir hasilnya cukup berbeda. Teorema dalam [KSTW01] yang saya sebutkan dalam jawaban ini adalah tentang versi kelengkapan sempurna sedangkan hasil Raghavendra tidak. Teorema dalam [KSTW01] adalah tentang CSP boolean, sedangkan Raghavendra adalah tentang CSP pada domain apa pun. Tetapi Anda harus memeriksa sendiri, karena saya tidak tahu kertas oleh Raghavendra dengan baik.
Tsuyoshi Ito