Bolehkah masalah SAT menjadi masalah lengkap NP?
Persoalan sama ada masalah SAT (Boolean satisfiability) boleh menjadi masalah NP-lengkap adalah persoalan asas dalam teori kerumitan pengiraan. Untuk menangani perkara ini, adalah penting untuk mempertimbangkan definisi dan sifat kesempurnaan NP dan mengkaji konteks sejarah dan teori yang menyokong klasifikasi SAT sebagai masalah lengkap NP.
Definisi dan Konteks
Masalah SAT: Masalah SAT melibatkan penentuan sama ada wujud penetapan nilai kebenaran kepada pembolehubah yang menjadikan formula Boolean yang diberikan benar. Rumus Boolean biasanya dinyatakan dalam bentuk normal penghubung (CNF), di mana formulanya ialah gabungan klausa, dan setiap klausa ialah percabaran literal. Sebagai contoh, formula mungkin kelihatan seperti:
![\[ (x_1 \lor \neg x_2) \land (\neg x_1 \lor x_3) \land (x_2 \lor \neg x_3). \]](https://eitca.org/wp-content/ql-cache/quicklatex.com-8e405df3b02de2e85a91e7957c82bb5b_l3.png "Diberikan oleh QuickLaTeX.com")
NP (Masa Polinomial Tidak Tentu): Masalah keputusan adalah dalam NP jika penyelesaian yang diberikan boleh disahkan sebagai betul atau salah dalam masa polinomial oleh mesin Turing yang menentukan. Pada asasnya, jika anda mempunyai penyelesaian calon, anda boleh menyemak kesahihannya dengan cekap.
NP-Lengkap: Masalah adalah NP-lengkap jika ia memenuhi dua syarat:
1. Ia adalah dalam NP.
2. Setiap masalah dalam NP boleh dikurangkan kepadanya dalam masa polinomial.
Konsep kesempurnaan NP telah diperkenalkan oleh Stephen Cook dalam makalah seminalnya 1971 "The Complexity of Theorem-Proving Procedures," di mana beliau menunjukkan bahawa masalah SAT ialah masalah lengkap NP yang pertama diketahui. Keputusan ini kini dikenali sebagai Teorem Cook.
Teorem Cook dan Implikasinya
Untuk memahami mengapa SAT adalah NP-lengkap, kita perlu mewujudkan dua perkara utama:
1. SAT berada dalam NP.
2. Setiap masalah dalam NP boleh dikurangkan kepada SAT dalam masa polinomial.
SAT berada di NP
Untuk mengesahkan bahawa SAT berada dalam NP, pertimbangkan bahawa diberikan formula Boolean dan cadangan penugasan nilai kebenaran kepada pembolehubahnya, kita boleh menyemak sama ada formula itu bernilai benar dalam masa polinomial. Ini melibatkan penilaian setiap klausa dalam formula untuk melihat sama ada sekurang-kurangnya satu literal dalam setiap klausa adalah benar. Memandangkan menilai formula Boolean ialah proses mudah yang melibatkan bilangan operasi logik yang terhad, ia boleh dilakukan dengan cekap. Oleh itu, SAT berada dalam NP kerana kita boleh mengesahkan penyelesaian dalam masa polinomial.
Pengurangan Masa Polinomial
Bahagian yang lebih mencabar untuk membuktikan bahawa SAT adalah NP-lengkap menunjukkan bahawa setiap masalah dalam NP boleh dikurangkan kepada SAT dalam masa polinomial. Ini melibatkan menunjukkan bahawa untuk sebarang masalah dalam NP, terdapat fungsi pengiraan masa polinomial yang mengubah kejadian masalah menjadi contoh SAT supaya masalah asal mempunyai penyelesaian jika dan hanya jika contoh SAT yang diubah adalah memuaskan.
Untuk menggambarkan ini, pertimbangkan masalah generik 
dalam NP. Mengikut takrifan, wujud mesin Turing masa polinomial tidak tentu 
yang memutuskan . Mesin itu mempunyai proses pengesahan masa polinomial yang boleh menyemak sama ada sijil (penyelesaian) yang diberikan adalah sah. Kita boleh mengekod operasi pada sesuatu input 
sebagai formula Boolean supaya formula itu memuaskan jika dan hanya jika menerima .
Pengekodan melibatkan langkah-langkah berikut:
1. Pengekodan Konfigurasi: Mengekodkan konfigurasi (keadaan, kandungan pita, dan kedudukan kepala) bagi sebagai pembolehubah Boolean. Setiap konfigurasi boleh diwakili oleh urutan bit.
2. Pengekodan Peralihan: Mengekodkan fungsi peralihan bagi sebagai satu set kekangan Boolean. Kekangan ini memastikan peralihan yang sah antara konfigurasi ditangkap.
3. Negeri Awal dan Penerima: Mengekod konfigurasi awal (apabila mesin dimulakan) dan konfigurasi penerimaan (apabila mesin berhenti dan menerima) sebagai kekangan Boolean.
Dengan membina formula Boolean yang menangkap tingkah laku , kami mencipta contoh SAT yang memuaskan jika dan hanya jika terdapat urutan peralihan yang sah yang membawa kepada keadaan penerimaan. Pengurangan ini boleh dilakukan dalam masa polinomial berbanding saiz input .
Contoh: Pengurangan daripada 3-SAT kepada SAT
Untuk menjelaskan lagi konsep pengurangan masa polinomial, pertimbangkan kes khusus untuk mengurangkan 3-SAT kepada SAT. Masalah 3-SAT ialah kes khas SAT di mana setiap klausa mempunyai tepat tiga literal. Untuk mengurangkan 3-SAT kepada SAT, kita hanya boleh melihat bahawa mana-mana contoh 3-SAT sudah dalam bentuk yang diperlukan oleh SAT (iaitu, formula CNF). Oleh itu, pengurangan adalah remeh dan boleh dilakukan dalam masa linear, iaitu pengurangan masa polinomial.
Implikasi SAT Menjadi NP-Lengkap
Pengelasan SAT sebagai NP-lengkap mempunyai implikasi yang mendalam untuk teori kerumitan pengiraan dan penyelesaian masalah praktikal. Memandangkan SAT adalah NP-lengkap, sebarang masalah dalam NP boleh diterjemahkan ke dalam contoh SAT. Kesejagatan ini bermakna SAT berfungsi sebagai penanda aras untuk kerumitan masalah lain. Jika kita boleh mencari algoritma masa polinomial untuk menyelesaikan SAT, kita boleh menyelesaikan semua masalah NP dalam masa polinomial, membayangkan 
.
Sebaliknya, jika kita membuktikan bahawa tiada algoritma masa polinomial wujud untuk SAT, ia akan membayangkan bahawa 
. Walaupun penyelidikan yang luas, persoalan sama ada kekal sebagai salah satu masalah terbuka yang paling ketara dalam sains komputer.
Aplikasi praktikal
Dalam amalan, penyelesai SAT digunakan secara meluas dalam pelbagai domain, termasuk pengesahan perisian, kecerdasan buatan dan kriptografi. Penyelesai SAT moden memanfaatkan algoritma dan heuristik yang canggih untuk mengendalikan keadaan yang besar dan kompleks dengan cekap, walaupun NP-kelengkapan teori SAT. Penyelesai ini telah memungkinkan untuk menangani masalah dunia sebenar yang sebelum ini sukar diatasi.
Kesimpulan
Masalah SAT sememangnya merupakan masalah NP-lengkap, seperti yang ditetapkan oleh Teorem Cook. Pengelasan ini adalah berdasarkan fakta bahawa SAT berada dalam NP dan setiap masalah dalam NP boleh dikurangkan kepada SAT dalam masa polinomial. Implikasi SAT menjadi NP-lengkap adalah meluas, mempengaruhi kedua-dua penyelidikan teori dan aplikasi praktikal dalam sains komputer.
Soalan dan jawapan terbaru lain mengenai kerumitan:
- Adakah kelas PSPACE tidak sama dengan kelas EXPSPACE?
- Adakah kelas kerumitan P subset kelas PSPACE?
- Bolehkah kita membuktikan bahawa kelas Np dan P adalah sama dengan mencari penyelesaian polinomial yang cekap untuk sebarang masalah lengkap NP pada TM yang menentukan?
- Bolehkah kelas NP sama dengan kelas EXPTIME?
- Adakah terdapat masalah dalam PSPACE yang tiada algoritma NP yang diketahui?
- Bolehkah masalah berada dalam kelas kerumitan NP jika terdapat mesin turing bukan deterministik yang akan menyelesaikannya dalam masa polinomial
- NP ialah kelas bahasa yang mempunyai pengesah masa polinomial
- Adakah P dan NP sebenarnya adalah kelas kerumitan yang sama?
- Adakah setiap bahasa bebas konteks dalam kelas kerumitan P?
- Adakah terdapat percanggahan antara takrifan NP sebagai kelas masalah keputusan dengan pengesah masa polinomial dan fakta bahawa masalah dalam kelas P juga mempunyai pengesah masa polinomial?
Lihat lebih banyak soalan dan jawapan dalam Kerumitan