Kekerasan pendekatan - kesalahan aditif

Ada literatur yang kaya dan setidaknya satu buku yang sangat bagus menguraikan kekerasan yang diketahui hasil perkiraan untuk masalah NP-keras dalam konteks kesalahan multiplikasi (misalnya 2-perkiraan untuk penutup vertex optimal dengan asumsi UGC). Ini juga termasuk kelas kompleksitas perkiraan yang dipahami dengan baik seperti APX, PTAS dan sebagainya.

Apa yang diketahui kapan kesalahan aditif dipertimbangkan? Pencarian literatur menunjukkan beberapa hasil tipe upper bound, terutama untuk pengemasan bin (lihat misalnya http://www.cs.princeton.edu/courses/archive/spr03/cs594/dpw/lecture2.ps ), tetapi apakah ada klasifikasi kelas kompleksitas yang lebih komprehensif atau adakah alasan mengapa itu tidak begitu menarik atau relevan?

Sebagai komentar lebih lanjut, untuk pengemasan bin, misalnya, sejauh yang saya tahu tidak ada alasan teoritis mengapa algoritma waktu poli yang selalu dalam jarak aditif dari optimal 1 tidak dapat ditemukan (walaupun saya berdiri untuk dikoreksi ). Akankah algoritma seperti itu meruntuhkan kelas kompleksitas atau memiliki efek teori knock-on signifikan lainnya?

EDIT: Ungkapan kunci yang saya tidak gunakan adalah "kelas perkiraan asimptotik" (terima kasih Oleksandr). Tampaknya ada beberapa pekerjaan di bidang ini tetapi belum sampai pada tahap kematangan yang sama seperti teori kelas perkiraan klasik.

Pertanyaannya agak terbuka, jadi saya tidak berpikir itu bisa dijawab sepenuhnya. Ini adalah jawaban parsial.

Pengamatan yang mudah adalah bahwa banyak masalah tidak menarik ketika kita mempertimbangkan perkiraan aditif. Sebagai contoh, secara tradisional fungsi objektif dari masalah Max-3SAT adalah jumlah klausa yang puas. Dalam formulasi ini, kira-kira Max-3SAT dalam kesalahan aditif O (1) setara dengan memecahkan Max-3SAT secara tepat, hanya karena fungsi tujuan dapat diskalakan dengan menyalin formula input berkali-kali. Perkiraan multiplikatif jauh lebih penting untuk masalah semacam ini.

[Sunting: Dalam revisi sebelumnya, saya telah menggunakan Set Independen sebagai contoh pada paragraf sebelumnya, tetapi saya mengubahnya ke Max-3SAT karena Independent Set bukan contoh yang baik untuk menggambarkan perbedaan antara pendekatan multiplikatif dan pendekatan aditif; mendekati Set Independen bahkan dalam faktor multiplikasi O (1) juga NP-hard. Faktanya, ketidaksepakatan yang jauh lebih kuat untuk Independent Set ditunjukkan oleh Håstad [Has99].]

Tetapi, seperti yang Anda katakan, perkiraan aditif menarik untuk masalah seperti pengemasan bin, di mana kami tidak dapat mengukur fungsi objektif. Selain itu, kita sering dapat merumuskan kembali masalah sehingga pendekatan aditif menjadi menarik.

Misalnya, jika fungsi objektif Max-3SAT didefinisikan ulang sebagai rasio jumlah klausa yang puas terhadap jumlah klausa total (seperti yang kadang-kadang dilakukan), pendekatan aditif menjadi menarik. Dalam pengaturan ini, aproksimasi aditif tidak lebih sulit daripada aproksimasi multiplikatif dalam arti bahwa aproksibilitas dalam faktor multiplikasi 1− ε (0 < ε <1) menyiratkan aproksimasi dalam kesalahan aditif ε , karena nilai optimal selalu paling banyak 1.

Fakta menarik (yang tampaknya sayangnya sering diabaikan) adalah bahwa banyak hasil yang tidak dapat diperkirakan membuktikan kelengkapan NP dari masalah kesenjangan tertentuyang tidak mengikuti hanya dari NP-hardness dari pendekatan multiplikasi (lihat juga Petrank [Pet94] dan Goldreich [Gol05, Bagian 3]). Melanjutkan contoh Max-3SAT, itu adalah hasil yang terkenal oleh Håstad [Has01] bahwa NP-sulit untuk memperkirakan Max-3SAT dalam faktor multiplikasi konstan yang lebih baik dari 7/8. Hasil ini saja tampaknya tidak menyiratkan bahwa NP-sulit untuk memperkirakan versi rasio Max-3SAT dalam kesalahan aditif konstan di luar batas tertentu. Namun, apa yang dibuktikan oleh Håstad [Has01] lebih kuat daripada sekadar ketidak-taksiran multiplikatif belaka: ia membuktikan bahwa masalah janji berikut ini adalah NP-complete untuk setiap konstanta 7/8 < s <1:

Gap-3SAT _'s
Instance : Formula CNF φ di mana setiap klausa melibatkan tepat tiga variabel berbeda.
Ya-janji : φ memuaskan.
No-janji : Tidak ada kebenaran tugas memenuhi lebih dari s sebagian kecil dari klausul φ.

Dari ini, kita dapat menyimpulkan bahwa NP-sulit untuk memperkirakan versi rasio Max-3SAT dalam kesalahan aditif lebih baik dari 1/8. Di sisi lain, tugas acak sederhana yang biasa memberikan perkiraan dalam kesalahan aditif 1/8. Oleh karena itu, hasil oleh Håstad [Has01] tidak hanya memberikan ketidaksimetrisan multiplikasi yang optimal untuk masalah ini, tetapi juga ketidaksungguhan aditif yang optimal. Saya kira ada banyak hasil tambahan yang tidak dapat diperkirakan seperti ini yang tidak muncul secara eksplisit dalam literatur.

Referensi

[Gol05] Oded Goldreich. Tentang masalah yang dijanjikan (survei untuk mengenang Shimon Even [1935-2004]). Kolokium Elektronik tentang Kompleksitas Komputasi , Laporan TR05-018, Februari 2005. http://eccc.hpi-web.de/report/2005/018/

[Has99] Johan Håstad. Klik sulit untuk diperkirakan dalam n ^{1− ε} . Acta Mathematica , 182 (1): 105–142, Maret 1999. http://www.springerlink.com/content/m68h3576646ll648/

[Has01] Johan Håstad. Beberapa hasil tidak optimal yang optimal. Jurnal ACM , 48 (4): 798-859, Juli 2001. http://doi.acm.org/10.1145/502090.502098

[Pet94] Erez Petrank. Kerasnya perkiraan: Celah lokasi. Kompleksitas Komputasi , 4 (2): 133–157, April 1994. http://dx.doi.org/10.1007/BF01202286

Ini adalah jawaban parsial

$ABS$$ABS$

$NP$

-Setiap grafik kubik adalah tepi 4-warna dalam waktu polinomial tetapi tepi 3-warna NP-keras.

$ABS$$P=NP$

Ada karya terbaru tentang kelas perkiraan asimptotik dan perbandingannya dengan rekan-rekan klasik.

Erik Jan van Leeuwen dan Jan van Leeuwen. Struktur Perkiraan Polinomial-Waktu . Laporan Teknis UU-CS-2009-034. Desember 2009.