Kekerasan pendekatan tanpa teorema PCP

36

Aplikasi penting dari teorema PCP adalah bahwa ia menghasilkan hasil jenis "kekerasan perkiraan". Dalam beberapa kasus yang relatif lebih sederhana seseorang dapat membuktikan kekerasan seperti itu tanpa PCP. Namun, adakah kasus di mana kekerasan hasil perkiraan pertama kali terbukti menggunakan teorema PCP, yaitu, hasilnya tidak diketahui sebelumnya, tetapi kemudian ditemukan bukti yang lebih langsung yang tidak bergantung pada PCP? Dengan kata lain, apakah ada kasus di mana PCP muncul pertama kali diperlukan, tetapi kemudian bisa dihilangkan?

cc.complexity-theory approximation-hardness pcp Andras Farago
sumber

35

Contohnya adalah makalah ini:

Guruswami, V., & Khanna, S. (2004). Pada kekerasan 4-warna, sebuah grafik 3-warna. Jurnal SIAM pada Matematika Diskrit , 18 (1): 30-40. link

Menggunakan PCP-Teorema, Khanna, Linial, dan Safra (2000) membuktikan bahwa NP-hard untuk mewarnai grafik 3-warna hanya menggunakan 4 warna. Kemudian, Guruswami & Khanna (2004) memberi, di antara hal-hal baik lainnya, bukti PCP-free untuk hasil yang sama.

vb le
sumber

11

Apakah Anda bersedia untuk mendeskripsikan artikel dalam jawaban Anda, daripada hanya menunjuk dengan hyperlink?

Niel de Beaudrap

15

Untuk masalah jalur disjoint edge maksimum dalam grafik berarah, makalah Ma & Wang (2000) didasarkan pada masalah label cover yang pada gilirannya didasarkan pada teorema PCP. Selanjutnya pengurangan sederhana melalui kekerasan masalah 2-disjointpath ditemukan oleh Guruswami et. Al. (2003) yang memberikan peningkatan kekerasan juga.

Chandra Chekuri
sumber

Tetapi apakah kekerasan 2-disjointpath memerlukan PCP?

Suresh Venkat

3

(s_{1}, t_{1})

$(s_1,t_1)$

(s_{2}, t_{2})

$(s_2,t_2)$

G

$G$

13

Ada contoh dari perkiraan penghitungan. Kira-kira menghitung jumlah penugasan yang memuaskan dari suatu hubungan NP hanya bisa lebih sulit daripada memutuskan apakah ada penugasan yang memuaskan ada, jadi tidak terlalu mengejutkan bahwa seseorang tidak memerlukan teorema PCP untuk membuktikan kekerasan untuk masalah seperti itu. Namun, teorema PCP kadang-kadang memberikan titik awal yang nyaman, misalnya, untuk makalah ini tentang kira-kira menghitung jumlah set independen dalam grafik jarang: http://www.dcs.ed.ac.uk/home/mrj/papers/ DFJ02.pdf Kemudian, Sly membuktikan hasil kekerasan untuk kira-kira menghitung set independen hanya berdasarkan standar NP-kekerasan Max-Cut: http://arxiv.org/pdf/1005.5584v1.pdf

Dana Moshkovitz
sumber

1

Menarik - apakah UGC meningkatkan kekerasan Sly tentang faktor aproksimasi di sini? (Sunting: Saya kira tidak; dia mengklaim

d = 6

$d=6$ optimal. Edit2: Kecuali Anda bisa mengesampingkan sesuatu yang lebih kuat dari PTAS? Adakah ide jika MAX-CUT's ketidaksimetrisan menyiratkan sesuatu untuk partisi?)

Daniel Apon

2

@DanielApon: hasil di kemudian hari menggunakan ketidak-taksiran MAX-CUT untuk memberikan hasil yang tidak dapat diperkirakan lebih kuat lagi: arxiv.org/abs/1203.2602 menunjukkan bahwa untuk beberapa

c

$c$ itu NP-sulit untuk kira-kira menghitung set independen dalam grafik 6-reguler ke dalam rasio

e^{c n}

$e^{cn}$ . Saya tidak berpikir nilai optimal

c

$c$ telah diselidiki, di bawah UGC atau lainnya.

Colin McQuillan

10

Jawaban lain, yang dalam semangat yang agak berbeda dari jawaban sebelumnya, adalah makalah ini Uri Feige: Hubungan antara Kompleksitas Kasus Rata-rata dan Kompleksitas Approximation .

Uri menunjukkan bahwa asumsi kasus rata-rata dapat menggantikan teorema PCP untuk membuktikan kekerasan perkiraan beberapa masalah. Namun, perlu diketahui bahwa kami tidak tahu bagaimana membuktikan asumsi kasus rata-rata, dan kami memiliki beberapa bukti bahwa kami tidak akan dapat membuktikannya berdasarkan asumsi kekerasan NP standar (lihat makalah Feigenbaum-Fortnow, Bogdanov-Trevisan, dll).

Dana Moshkovitz
sumber

Kekerasan pendekatan tanpa teorema PCP

Jawaban: