Mengapa masalah NP-complete tidak memiliki rasio perkiraan yang sama?

Karena 2 masalah NP-lengkap secara definisi dapat direduksi satu sama lain, sehingga solusi untuk salah satunya dapat diperoleh dengan menggunakan kotak hitam untuk menyelesaikan yang lain, mengapa mereka tidak memiliki rasio pendekatan yang sama (merujuk pada mitra pengoptimalannya) )? Saya kira beberapa drift polinomial konstan atau bahkan dapat dipahami tetapi kami memiliki kasus algoritma aproksimasi faktor konstan untuk beberapa masalah NP-lengkap dan, di sisi lain, masalah lain yang bahkan tidak dapat didekati oleh algoritma aproksimasi rasio polinomial-rasio , seperti TSP umum? Terima kasih

cc.complexity-theory approximation-algorithms reductions N27
sumber

karena pengurangan kotak hitam hanya mempertahankan aspek YA / TIDAK dari masalah (keputusan), bukan kedekatan perkiraan.

Suresh Venkat

jika saya mengurangi 3SAT ke penutup simpul, maka penutup simpul ukuran k menyiratkan kepuasan dan sebaliknya. Tetapi jika saya mendapatkan penutup simpul ukuran 2k, itu tidak berarti saya dapat memenuhi setengah klausa.

Suresh Venkat

Pilih pengurangan spesifik dari satu masalah NP-selesai yang lain, dan cobalah untuk memperpanjangnya untuk mempertahankan rasio perkiraan. Anda akan melihat apa yang salah.

Peter Shor

Jawaban Peter adalah yang terbaik. Coba saja dan lihat apa yang terjadi. Saya pikir dengan skeptisisme filosofis maksud Anda 'Saya tidak benar-benar mendapatkan intuisi'. Terkadang cara terbaik adalah mencoba beberapa contoh dan membiarkan intuisi tumbuh.

Suresh Venkat

\log | C |

$\log |C|$

| C |

$|C|$

| C |^{2}

$|C|^2$

2^{| C |}

$2^{|C|}$

C

$C$

Jukka Suomela

Jawaban:

Pengurangan didefinisikan sehubungan dengan versi keputusan dari masalah. Rasio perkiraan untuk versi optimisasi mereka adalah pertanyaan terpisah, yang tampaknya terkait tetapi tidak harus seperti itu. Jadi untuk menjawab pertanyaan Anda dengan pertanyaan, dari perspektif filosofis, mengapa Anda harus mengharapkan NPC kelas untuk mempertahankan rasio perkiraan ketika itu tidak didefinisikan sehubungan dengan mereka di tempat pertama?

Lev Reyzin
sumber

"Pengurangan didefinisikan sehubungan dengan versi keputusan dari masalah." Apakah ini benar, katakanlah pengurangan Levin ?

MS Dousti

Anda benar, tidak semua pengurangan didefinisikan oleh versi keputusan tertulis, tetapi kita dapat mendefinisikan NPC hanya dalam hal pengurangan kotak-hitam, dan kemudian saya kira itu dapat menyebabkan perdebatan tentang bagaimana kelas-kelas ini berubah dengan pengurangan yang digunakan ... Saya seharusnya mengatakan "kelas NPC didefinisikan untuk masalah keputusan." Ini sebenarnya bukan argumen yang tepat, karena kita bahkan dapat mendefinisikan kelas masalah keputusan yang versi optimisasinya mempertahankan rasio perkiraan, tapi bukan itu yang kita lakukan untuk kelas NPC. Saya kira pertanyaan yang diberikan @ N27 adalah keberatan filosofis, saya diizinkan untuk memberikan tanggapan filosofis. :)

Lev Reyzin