Mengapa masalah NP-complete sangat berbeda dalam hal perkiraan mereka?

Saya ingin memulai pertanyaan dengan mengatakan saya seorang programmer, dan saya tidak memiliki banyak latar belakang dalam teori kompleksitas.

Satu hal yang saya perhatikan adalah bahwa sementara banyak masalah adalah NP-lengkap, ketika diperluas ke masalah optimasi, beberapa jauh lebih sulit untuk diperkirakan daripada yang lain.

Contoh yang baik adalah TSP. Meskipun semua jenis TSP lengkap NP, masalah optimisasi yang sesuai menjadi lebih mudah dan lebih mudah untuk diperkirakan dengan penyederhanaan berturut-turut. Kasus umum adalah lengkap NPO, kasus metrik lengkap APX, dan kasus Euclidean sebenarnya memiliki PTAS.

Ini tampaknya kontra-intuitif bagi saya, dan saya bertanya-tanya apakah ada alasan untuk ini.

Salah satu alasan mengapa kita melihat kompleksitas perkiraan yang berbeda untuk masalah NP-complete adalah bahwa kondisi yang diperlukan untuk NP-complete merupakan ukuran yang sangat kasar dari kompleksitas masalah. Anda mungkin akrab dengan definisi dasar masalah menjadi NP-complete:$\Pi$

1. dalam NP, dan$\Pi$
2. Untuk setiap masalah lain dalam NP, kita dapat mengubah instance x dari Ξ menjadi instance y dari Π dalam waktu polinomial sehingga y adalah instance-ya dari Π jika dan hanya jika x adalah instance-ya dari Ξ .$\Xi$$x$$\Xi$$y$$\Pi$$y$$\Pi$$x$$\Xi$

Pertimbangkan kondisi 2: semua yang diperlukan adalah kita dapat mengambil dan mengubahnya menjadi beberapa y yang mempertahankan jawaban "satu-bit" ya / tidak. Tidak ada ketentuan tentang, misalnya, ukuran relatif saksi terhadap ya atau tidak (yaitu, ukuran solusi dalam konteks optimisasi). Jadi satu-satunya ukuran yang digunakan adalah ukuran total input yang hanya memberikan kondisi yang sangat lemah pada ukuran solusi. Jadi cukup "mudah" untuk mengubah Ξ menjadi Π .$x$$y$$\Xi$$\Pi$

Kita dapat melihat perbedaan dalam berbagai masalah NP-complete dengan melihat kompleksitas dari beberapa algoritma sederhana. -Coloring memiliki kekuatan kasar O ( k n ) (di mana n adalah ukuran input). Untuk k -Dominating Set, pendekatan kekerasan take O ( n k ) . Ini adalah, pada dasarnya, algoritma tepat terbaik yang kami miliki. k -Vertex Cover memiliki O yang sangat sederhana ( 2 k n c$k$$O(k^{n})$$n$$k$$O(n^{k})$$k$$O(2^{k}n^{c})$algoritme (pilih tepi, cabang tempat titik akhir untuk disertakan, tandai semua tertutup, teruskan sampai Anda tidak memiliki tepi yang tidak ditandai atau Anda menekan anggaran dan bactrack). Di bawah pengurangan banyak-waktu polinomial (pengurangan Karp, yaitu apa yang kita lakukan dalam kondisi 2 di atas), masalah-masalah ini setara.$k$

Ketika kita mulai mendekati kompleksitas dengan alat yang bahkan sedikit lebih rumit (kompleksitas aproksimasi, kompleksitas parameter, yang lainnya yang tidak dapat saya pikirkan), pengurangan yang kami gunakan menjadi lebih ketat, atau lebih tepatnya, lebih peka terhadap struktur solusi, dan perbedaan mulai muncul; -Vertex Cover (seperti yang Yuval sebutkan) memiliki perkiraan 2 sederhana (tetapi tidak memiliki FPTAS kecuali beberapa kelas kompleksitas runtuh), k -Dominating Set memiliki ( 1 + log n ) -aplikasi algoritma (tapi tidak ada ( c log n ) -approximation untuk beberapa c > $k$$k$$(1+\log n)$$(c\log n)$$c>0$), dan aproksimasi sama sekali tidak masuk akal untuk versi lurus ke depan dari -Coloring.$k$

$O(\log n)$$1/2 + k/n$$k$$O(1)$ algoritma aproksimasi.

Contoh-contoh ini tidak sepenuhnya dibuat-buat. Masalah MAX-INDEPENDENT-SET (setara dengan MAX-CLIQUE) dan MIN-VERTEX-COVER terkait erat - komplemen dari set independen adalah penutup vertex. Tetapi sementara yang pertama sulit untuk diperkirakan, yang terakhir memiliki 2-pendekatan sederhana.

Pengurangan yang menunjukkan NP-hardness dari masalah yang diberikan kadang-kadang dapat digunakan juga untuk menunjukkan kekerasan perkiraan, tetapi ini tidak selalu terjadi - tergantung pada pengurangan Sebagai contoh, pengurangan dari MAX-INDEPENDENT-SET ke MIN-VERTEX-COVER tidak menyiratkan kekerasan perkiraan masalah yang terakhir, yang jauh lebih mudah untuk diperkirakan daripada yang sebelumnya.

Ringkasnya, kekerasan-NP hanyalah salah satu aspek dari masalah. Kekerasan aproksimasi adalah aspek yang berbeda, dan itu sangat tergantung pada gagasan aproksimasi.

Sebagai pendekatan intuitif, pertimbangkan bahwa instantiasi masalah NP-complete tidak selalu sesulit kasus umum. Binary satisifiability (SAT) adalah NP-complete, tetapi sepele untuk menemukan solusi untuk A v B v C v D v ... Algoritma kompleksitas hanya mengikat kasus terburuk, bukan kasus rata-rata, atau bahkan kasus 90% .

Cara termudah untuk mengurangi masalah NP-lengkap menjadi sesuatu yang lebih sederhana adalah dengan hanya mengecualikan bagian-bagian yang sulit. Itu curang, ya. Tetapi seringkali bagian yang tersisa masih berguna untuk memecahkan masalah dunia nyata. Dalam beberapa kasus, garis antara "mudah" dan "sulit mudah untuk ditarik. Seperti yang Anda tunjukkan untuk TSP, ada pengurangan yang kuat dalam kesulitan saat Anda membatasi masalah di sekitar arah" normal "yang mungkin dipikirkan orang. Untuk masalah lain , lebih sulit untuk menemukan cara berguna kehidupan nyata untuk memisahkan bagian yang mudah dan sulit.

Untuk benar-benar meninggalkan ranah CS dan matematika, pertimbangkan sebuah mobil tua. Temanmu ingin mengendarainya. Jika Anda harus memberitahunya, "hei, mobilnya berfungsi sempurna. Hanya saja, jangan naik di atas 95mph. Ada goyangan jahat yang akan menjatuhkan Anda dari jalan," mungkin itu bukan masalah besar. Teman Anda mungkin hanya ingin membawanya berkeliling kota saja. Namun, jika Anda harus mengatakan kepadanya, "Anda harus menggunakan kopling tepat untuk beralih dari tanggal 1 ke 2, atau mesin akan berhenti," mungkin akan lebih sulit bagi teman Anda untuk menggunakan mobil di sekitar kota tanpa sedikit pelatihan.

Demikian juga, jika masalah NP-lengkap terjadi hanya menjadi sulit dalam kasus-kasus eksotis, itu mengurangi kompleksitas lebih cepat ketika Anda melihat subdomain. Namun, jika semakin sulit dalam kasus yang umum terjadi, tidak ada banyak subdomain berguna yang menghindari bagian yang sulit.