Saya mencoba (secara intuitif) memahami dua istilah "decidability" dan "verifiability".
Saya telah melakukan banyak pencarian dan pencarian berbagai teks yang dapat saya lakukan. Namun, pemahaman intuitif mereka nampaknya lepas dari saya, khususnya untuk yang kedua.
Dari banyak definisi yang ditemukan, yang berikut ditemukan di halaman ini , dengan jelas menjelaskan kepatutan kepada saya.
Suatu bahasa disebut decidable jika ada metode - metode apa saja - untuk menentukan apakah suatu kata termasuk dalam bahasa itu atau tidak.
Namun, saya gagal menemukan definisi paralel untuk verifikasi.
Dalam buku Theory of Computation oleh Sipser , kita menemukan,
P = kelas bahasa yang keanggotaannya dapat diputuskan dengan cepat.
NP = kelas bahasa yang keanggotaannya dapat diverifikasi dengan cepat.
Sehubungan dengan hal di atas, saya ingin memahami kebenaran.
Tolong berikan sebanyak mungkin contoh, pada satu saat, saya mencoba menangkap artinya, di yang berikutnya, saya menjadi bingung lagi.
Jawaban:
Kunci untuk memahami di sini adalah bahwa P dan NP adalah kelas masalah keputusan. Itu berarti bahwa mereka semua memiliki jawaban ya / tidak.
Jadi, ketika kita mengatakan masalah seperti 3-SAT adalah NP-Lengkap, itu berarti diberi contoh 3-SAT (alias kata berpotensi dalam bahasa), tidak ada cara efisien yang diketahui untuk menguji apakah kata itu atau tidak dalam bahasa
Mengatakan sesuatu dalam NP berarti ada semacam "bukti" untuk setiap string dalam bahasa, yang jumlahnya banyak dalam panjang input.
Misalnya, dalam 3-SAT, kami bertanya, apakah ada penugasan True / False untuk satu set variabel dalam rumus boolean, sehingga rumus itu ternyata benar. Kata yang kami uji adalah rumus boolean. Tidak ada cara yang diketahui untuk menemukan apakah ada solusi tunggal yang membuat seluruh formula benar. Tetapi, jika kita memiliki satu set nilai true / false untuk variabel, sangat mudah untuk memeriksa (dalam waktu polinomial) jika itu menyebabkan rumus untuk mengevaluasi ke true.
Poin kunci di sini adalah bahwa kata yang kami uji BUKAN nilai benar / salah untuk setiap variabel. Kata yang kami uji adalah rumus yang berisi variabel, dan bahasa adalah himpunan semua rumus boolean yang dievaluasi menjadi true.
Kami tidak tahu cara menguji secara efisien apakah kata (rumus) dalam bahasa (dapat dievaluasi menjadi benar), tetapi mengingat serangkaian penugasan benar / salah, kami dapat memverifikasi jika kata itu dievaluasi dengan benar yaitu "bukti" "Bahwa kata (formula) ada dalam bahasa. Dengan demikian masalahnya ada di NP, tetapi tidak diketahui berada di P.
NP sebenarnya adalah kelas masalah keputusan polinomial yang tidak dapat diputuskan. Ini karena, dalam mesin turing non-deterministik, kami memiliki poin "keputusan" di mana kami dapat mengambil salah satu dari beberapa tindakan, dan pemberi sertifikat polinomial kami pada dasarnya hanya memberi tahu keputusan mana yang harus diambil pada setiap titik keputusan.
sumber
misalkan Anda memberi saya masalah dan Anda bertanya kepada saya solusinya jadi katakanlah Anda hanya dapat memeriksa jumlah polinomial bukti saya (yaitu: Anda dapat menjalankan program komputer yang efisien pada bukti saya) ketika saya mengirimi Anda bukti solusi itu semua apa yang Anda lakukan adalah menjalankan program Anda dan memutuskan sesuai dengan apa output program.
misalnya: misalkan Anda bertanya kepada saya apakah grafik 3-warna, maka apa yang harus saya lakukan adalah mengirim 3 pewarnaan grafik maka Anda memeriksa apakah semua simpul yang berdekatan memiliki warna yang berbeda maka pewarnaannya legal dan program berakhir dengan "accept" (kalau tidak buktinya tidak diterima dan kami akhiri dengan "tolak").
yang dipanggil untuk memverifikasi "dengan cepat".
jika Anda dapat membangun "program komputer" efisien "(atau hanya: algoritma polinomial) yang mengatakan jika input (string panjang n) dalam bahasa (atau jika output program 1 \" terima ") inilah yang maksudnya dengan kompleksitas kelas P.
contoh: misalkan saya memberi Anda daftar string (katakanlah buku telepon) dan bertanya kepada Anda tentang nama yang harus Anda katakan apakah itu ada di dalam buku atau tidak. salah satu solusinya adalah dengan membuang semua nama dan membandingkan setiap nama dengan nama yang diberikan, yang mengatakan Anda dapat menyelesaikannya dalam waktu linier.
contoh lain adalah: diberi grafik G = (V, E) dan sebuah tepi e = (u, v) dan Anda ingin mengatakan jika ujungnya ada di grafik.
sumber