Bukti NP-hardness: mencari beberapa masalah np-hard terbatas yang bagus

8

Untuk menunjukkan NP-hardness dari suatu masalah, seseorang perlu memilih masalah NP-hard yang diketahui dan menemukan pengurangan polinomial dari masalah yang diketahui ke masalahnya. Secara teoritis, setiap masalah NP-hard dapat digunakan untuk pengurangan, tetapi dalam praktiknya, beberapa masalah lebih mudah dikurangi daripada yang lain.

Misalnya, 3-SAT biasanya merupakan pilihan yang lebih baik untuk membangun pengurangan daripada SAT karena yang pertama lebih terbatas daripada yang terakhir, 3-partisi biasanya merupakan pilihan yang lebih mudah daripada pengepakan bin, ...

Salah satu cara untuk menemukan masalah "baik" untuk reduksi adalah dengan melakukan analisis statistik atas pengurangan yang ada. Misalnya, seseorang dapat membentuk semua pasangan from -> topengurangan buku Komputer dan Keterbukaan: Panduan untuk Teori Kelengkapan NP (atau sumber daya lainnya) dan menggambar histogram dari masalah dalam fromset. Lalu kita bisa mencari tahu masalah mana yang lebih umum digunakan untuk reduksi.

Saya ingin tahu apakah analisis statistik seperti itu masuk akal sama sekali. Apakah penelitian semacam itu sudah dilakukan atau belum? Jika tidak, apa tebakan Anda tentang masalah yang paling umum digunakan untuk pengurangan.

Alasan saya mengajukan pertanyaan ini adalah bahwa saya telah melakukan beberapa bukti kekerasan NP, tetapi hampir semuanya bergantung pada pengurangan dari masalah yang sama (3-partisi). Saya mencari opsi lain untuk digunakan dalam bukti saya.

np-hardness reductions Helium
sumber
1
Dari pengalaman kecil saya, saya pikir itu tergantung pada domain masalah yang Anda hadapi (aritmatika, teori grafik, penjadwalan, teka-teki, ..); pertama-tama Anda harus mencari masalah NPC yang serupa atau terkait untuk melihat apakah ada masalah yang baik untuk memulai FROM (misalnya klasifikasi A1-A12 dari G&J); kemudian lihat bukti NPC mereka untuk mendapatkan petunjuk / wawasan tentang arah yang bisa Anda ikuti; akhirnya jika tidak ada yang keluar coba gunakan masalah NPC "tingkat rendah" sederhana yang tidak memerlukan struktur rumit (3SAT, 1 dalam 3 SAT, Planar SAT, Exact Cover oleh Tiga Set, 3-pewarnaan, 3-partisi, siklus Ham dalam grafik planar atau grid, ..)
Marzio De Biasi
@MarzioDeBiasi: Anda benar tapi saya pikir mencari di antara ribuan masalah untuk menemukan yang tepat adalah pekerjaan yang melelahkan. Pemeringkatan berdasarkan jumlah reduksi yang saya sarankan memberi kita petunjuk tentang dari mana memulai pencarian kita. Bahkan, kami biasanya tidak memilih masalah secara acak. Kami biasanya memilih masalah berdasarkan kesamaan (apakah itu kata yang baik?) Dan berdasarkan frekuensi pengurangan yang telah kami lihat dari masalah itu. Saya hanya ingin membuat pilihan ini sedikit lebih formal atau setidaknya mendapatkan beberapa saran dari para ahli di daerah tentang masalah favorit mereka.
Helium
@MarzioDeBiasi: omong-omong, daftar masalah yang Anda sebutkan di komentar Anda juga berguna bagi saya.
Helium
1
@MarzioDeBiasi, saya pikir itu sangat bagus jika Anda membagikan pengalaman Anda sebagai jawaban, Anda adalah salah satu yang terbaik tentang bukti kekerasan di cstheory.SE.
Saeed
1
dengarkan dengan cermat MDB re G&J. mereka mengatur jenis masalah menjadi beberapa bagian. mungkin ada ribuan varian masalah NP lengkap tetapi mereka berada di tema dasar / genre / bagian. grafik besar akan menarik untuk dibangun tetapi tidak terlalu statistik. mungkin mengeluarkan struktur dunia kecil di mana ada "hub" utama. G&J sendiri mendaftar hub utama di berbagai bab / bagian.
vzn

Jawaban:

6

Saya tidak tahu apakah ada cara mesin untuk melakukan ini, tetapi pengalaman pribadi kecil saya bekerja sebagai berikut.

Saya mencoba memberikan algoritma waktu polinomial untuk suatu masalah. Dalam percobaan tersebut biasanya saya dapat melihat ada beberapa versi terbatas dari masalah yang dapat dipecahkan dengan waktu polinomial. Saya juga akan mengerti bagian algoritma yang saya tangani untuk masalah aslinya. Saya dapat membandingkan dua kasus ini (perbedaan antara versi terbatas dan yang umum juga merupakan bagian dari algoritma yang sulit untuk diperbaiki). Dengan membandingkan kedua kasus tersebut, biasanya mungkin untuk menebak bagaimana masalah bottleneck itu. Jadi kita bisa menemukan masalah sulit terkait. Biasanya menyediakan algoritma untuk suatu masalah adalah pekerjaan berat, dan membutuhkan pengetahuan yang baik tentang suatu masalah. Setelah kita mendapatkan pengetahuan tentang masalah ini, kita dapat memiliki banyak ide berbeda untuk mengatasi masalah dalam skenario yang berbeda (bukan hanya hasil kekerasan).

PS: Kalau buktinya ada pada masalah tertentu, saya kira itu karena masalah itu sangat dekat dengan pekerjaan Saudara, jadi jangan salahkan diri sendiri.

Saeed
sumber
2
+1: Saya setuju bahwa mencari algoritme waktu adalah titik awal yang baik dan mengungkapkan rahasia tentang masalah
Helium