Pertanyaan ini terkait erat dengan posting lain: Fase Transisi dalam Masalah Keras NP tetapi agak berbeda. Sementara pertanyaan itu adalah tentang kekerasan dari kasus-kasus khusus masalah sulit NP, ini adalah tentang peringkat kesulitan dari kasus yang sama.
Ada banyak bibliografi tentang efek yang dikenal sebagai Transisi Fase . Khususnya untuk kasus rumus 3-SAT acak dalam Conjunctive Normal Form (CNF), diketahui bahwa ada nilai R dari rasio klausa terhadap variabel sehingga untuk semua r <R formula dapat dipenuhi dengan probabilitas tinggi dan untuk r> R formula tidak memuaskan dengan probabilitas tinggi. Efek Transisi Fase terjadi di dekat R dan memiliki efek luar biasa yang memecahkan masalah kepuasan untuk formula tersebut sangat sulit dalam praktiknya.
Karena untuk membuktikan kekerasan NP dari masalah tertentu, perlu untuk menunjukkan bahwa ada waktu polinom Turing-reduksi untuk itu dari masalah NP-lengkap dan bahwa masalah yang NP-lengkap dapat ditransformasikan dalam waktu polinomial di antara mereka, maka pertanyaan berikut muncul secara alami:
Apakah mungkin untuk menentukan tingkat kesulitan masalah sulit NP dalam praktek menggunakan Transisi Fase CNF 3-SAT sebagai indikator? Intuisi adalah bahwa satu masalah P1 dapat diharapkan lebih sulit daripada P2 jika pengkodeannya 3-SAT lebih dekat R (yang dikenal dekat 4.2). Perhatikan bahwa ide ini tidak selalu mengikat setiap contoh ke kesulitan tertentu, itu hanya peringkat mereka.
Ada sejumlah argumen balasan, di antaranya:
- Transisi Fasa dari rumus CNF 3-SAT berlaku untuk rumus acak. Namun, contoh khusus dalam masalah yang berbeda memiliki beberapa struktur yang dapat dieksploitasi oleh pemecah untuk masalah itu --- ini sudah ditunjukkan oleh Peter Shor dalam pertanyaan tersebut.
- Mungkin terjadi bahwa pengkodean tertentu yang digunakan untuk mengubah contoh-contoh tertentu dalam masalah kita menjadi 3-SAT memainkan peran penting dalam rasio klausa terhadap variabel yang mengarah ke nilai yang menyesatkan, karenanya kesalahan klasifikasi --- keprihatinan ini diajukan oleh Kaveh dalam komentar untuk pertanyaan ini.
- Serge (menurut pemahaman saya dari komentarnya terhadap pertanyaan ini) memunculkan isu bahwa orang mungkin secara artifisial mempersulit masalah NP asli sehingga menghasilkan formula 3CNF yang mengubah rasio klausa terhadap variabel sambil mempertahankan kepuasan.
Sedangkan untuk 1, semua masalah mungkin memiliki kelas keteraturan yang sama sehingga masalah peringkat (alih-alih mengkarakterisasi kesulitan) mungkin berlaku; Adapun 2, ada pengkodean dalam masalah tertentu yang dikenal sebagai non-redundant wrt aturan Propagasi Unit sehingga mereka harus dipilih dan mungkin mereka menghindari kesalahan klasifikasi tersebut. Contohnya adalah Sideris et al., 2010 untuk kasus Perencanaan Proposisi. Adapun 3, Cheeseman et al., 1991 sudah mempertimbangkan masalah apakah pemetaan antara masalah mempertahankan atau tidak efek transisi fase dan percobaan pendahuluan mereka tampaknya mendukung dugaan mereka, asalkan seseorang mengurangi masalah NP asli dan bahkan " dapat selanjutnya dikurangi dengan menerapkan resolusi pada klausa ".
Apakah ini semua masuk akal bagi Anda? apakah Anda mengetahui adanya referensi bibliografi tentang ini? Bimbingan apa pun akan diakui!
sumber
Jawaban:
Meskipun tidak terbayangkan bahwa kendala teknis yang Anda sebutkan dapat diatasi, saya pikir ada sedikit motivasi saat ini untuk melakukannya, karena alasan sederhana bahwa (setidaknya sejauh yang saya ketahui) kesulitan NP-hard masalah dalam praktik tampaknya, secara empiris, tidak ada hubungannya dengan kedekatan mereka dengan transisi fase 3-SAT.
Bandingkan hal ini dengan beberapa cara lain untuk menentukan peringkat masalah NP-hard dalam hal kesulitan: Ada beberapa korelasi empiris antara masalah NP-hard yang mudah dalam praktiknya dan masalah NP-hard yang mudah diperkirakan , atau yang dapat diperbaiki dengan parameter tetap (dalam arti kompleksitas parameterized). Pengertian yang tepat tentang reduksi telah dikembangkan dalam kasus-kasus ini yang sebagian menjelaskan pengamatan empiris. Namun, saat ini tampaknya tidak ada indikasi empiris bahwa sebagian besar masalah NP-hard yang sulit dalam prakteknya sulit karena hubungan dekat mereka dengan contoh 3-SAT di dekat fase transisi. Jadi tidak masuk akal untuk mengembangkan teori untuk "menjelaskan" sesuatu yang tampaknya tidak benar dalam praktiknya.
sumber