Rule of thumb untuk mengetahui apakah suatu masalah bisa NP-lengkap

Pertanyaan ini terinspirasi oleh komentar di StackOverflow .

Selain mengetahui masalah NP-lengkap dari buku Garey Johnson, dan banyak lainnya; adakah aturan praktis untuk mengetahui apakah suatu masalah terlihat seperti masalah NP-complete?

Saya tidak mencari sesuatu yang ketat, tetapi untuk sesuatu yang bekerja dalam banyak kasus.

Tentu saja, setiap kali kita harus membuktikan bahwa suatu masalah adalah NP-complete, atau sedikit varian dari NP-complete; tetapi sebelum bergegas ke buktinya akan lebih baik untuk memiliki keyakinan tertentu pada hasil positif dari buktinya.

Ini adalah pendekatan pribadi saya untuk menentukan apakah suatu masalah (yaitu bahasa ) adalah NP-lengkap atau tidak. Jika kedua kondisi ini diverifikasi:$L$

• Saya merasa bahwa pengujian jika sebuah instance di L menyiratkan bahwa saya perlu memeriksa semua kombinasi$I$$L$
• dan bahwa tidak ada cara untuk membagi kombinasi seperti itu menjadi dua yang lebih kecil

lalu $L$ mungkin NP-hard.

$S$$S$$S_1$$S_2$$S_1$$S_2$ tetapi itu akan sangat lama ...

$A$$C$$B$$A$$B$$B$$C$

Sejujurnya pendekatan ini sangat mendasar: Saya mencoba mencari algoritma (polinomial) untuk masalah yang diberikan. Jika saya tidak dapat menemukan satu maka masalah menjadi "sulit" dalam sudut pandang saya. Kemudian muncul semua penalaran kelengkapan NP: apakah saya dapat menyandikan masalah NP-complete yang ada ke dalam masalah ini? (Dan karena ini biasanya jauh lebih sulit, saya mencoba sekali lagi untuk menemukan algoritma polinomial ..)

Saya curiga ini adalah cara berpikir yang biasa. Namun tetap sulit untuk diterapkan pada masalah yang tidak diketahui. Saya pribadi ingat dikejutkan oleh salah satu contoh pertama dari kelengkapan NP yang saya diberitahu: the masalah klik . Tampaknya sangat mudah untuk diperiksa! Jadi saya kira pengalaman itu ada hubungannya dengan itu. Intuisi juga terkadang tidak berguna. Saya ingat diberitahu beberapa kali dua masalah yang hampir identik tetapi satu di P dan yang lainnya dengan variasi kecil adalah NP-lengkap.

Saya belum menemukan contoh yang baik (saya butuh bantuan di sini), tetapi ini seperti masalah korespondensi pos : ini adalah masalah yang tidak dapat ditentukan tetapi beberapa varian dapat dipilih.

Perspektif lain tentang kekerasan-masalah datang dari komunitas permainan dan teka-teki, di mana aturan praktisnya adalah bahwa 'masalah sesulit mungkin' (dan pengecualian berasal dari struktur tersembunyi dalam masalah - contoh Massimo tentang penentu dalam komentar adalah contoh yang bagus untuk ini); Triknya adalah memahami seberapa sulit suatu masalah bisa terjadi:

• $n$
• Teka-teki yang melibatkan urutan gerakan dalam ruang keadaan terbatas ada di PSPACE (karena 'pindahkan pohon' secara umum dapat dieksplorasi dengan cara standar-pertama yang hanya membutuhkan penyimpanan untuk sejumlah konfigurasi polinomial), dan cenderung selesai-PSPACE; contoh klasik dari hal ini adalah Rush Hour.
• Game dengan kedalaman terikat polinomi juga di PSPACE; ini menggunakan karakterisasi PSPACE sebagai APTIME, karena karakterisasi minimum min-max dari strategi dengan sempurna meniru mesin Turing bergantian dengan karakterisasi sebagai 'ada gerakan untuk pemain A sehingga untuk setiap gerakan balasan dari pemain B, ada balasan pindah untuk pemain A sedemikian rupa sehingga ... ', dll. Mereka juga cenderung menyelesaikan PSPACE; Game Hex dan Tic-Tac-Toe yang digeneralisasi adalah contohnya.
• Permainan tanpa batas pada kedalaman pohon tetapi dimainkan dalam ruang yang dibatasi (secara polinomi) ada di EXPTIME, karena ada banyak posisi total secara eksponensial dan seluruh grafik dapat dibangun dan dieksplorasi dalam polinomial waktu dalam jumlah posisi (dan dengan demikian keseluruhan eksponensial) ; game-game ini umumnya EXPTIME-complete. Catur, catur, dan pergi semua termasuk dalam kategori ini.