NP ialah kelas bahasa yang mempunyai pengesah masa polinomial
Kelas NP, yang bermaksud "masa polinomial tidak tentu," ialah konsep asas dalam teori kerumitan pengiraan, subbidang sains komputer teori. Untuk memahami NP, seseorang mesti terlebih dahulu memahami tanggapan masalah keputusan, iaitu soalan dengan jawapan ya-atau-tidak. Bahasa dalam konteks ini merujuk kepada satu set rentetan di atas beberapa abjad, di mana setiap rentetan mengekod contoh masalah keputusan.
Bahasa (L) dikatakan berada dalam NP jika wujud pengesah masa polinomial untuk (L). Pengesah ialah algoritma penentu (V) yang mengambil dua input: contoh (x) dan sijil (y). Sijil (y) juga dikenali sebagai "saksi" atau "bukti." Pengesah (V) menyemak sama ada sijil (y) mengesahkan bahawa (x) kepunyaan bahasa (L). Secara formal, bahasa (L) berada dalam NP jika wujud algoritma polinomial-masa (V) dan polinomial (p(n)) supaya bagi setiap rentetan (x dalam L), wujud rentetan (y) dengan ( |y|. leq p(|x|)) dan (V(x, y) = 1). Sebaliknya, untuk setiap rentetan (x notin L), tiada rentetan (y) sedemikian rupa sehingga (V(x, y) = 1).
Untuk menjelaskan konsep ini, pertimbangkan masalah terkenal "Boolean satisfiability" (SAT). Masalah SAT menanyakan sama ada wujud penetapan nilai kebenaran kepada pembolehubah dalam formula Boolean yang diberikan supaya formula itu menilai kepada benar. Masalah SAT adalah dalam NP kerana, diberi formula Boolean ( phi ) dan penugasan ( alpha ) nilai kebenaran kepada pembolehubahnya, seseorang boleh mengesahkan dalam masa polinomial sama ada ( alpha ) memenuhi ( phi ). Di sini, contoh ( x ) ialah formula Boolean ( phi ), dan sijil ( y ) ialah tugasan ( alpha ). Pengesah ( V ) menyemak sama ada ( alpha ) menjadikan ( phi ) benar, yang boleh dilakukan dalam masa polinomial berkenaan dengan saiz ( phi ).
Satu lagi contoh ilustrasi ialah masalah "Laluan Hamilton". Masalah ini bertanya sama ada terdapat laluan dalam graf tertentu yang melawati setiap bucu tepat sekali. Masalah Laluan Hamiltonian juga dalam NP kerana, diberi graf ( G ) dan jujukan bucu ( P ), seseorang boleh mengesahkan dalam masa polinomial sama ada ( P ) ialah laluan Hamiltonian dalam ( G ). Dalam kes ini, contoh ( x ) ialah graf ( G ), dan sijil ( y ) ialah jujukan bucu ( P ). Pengesah ( V ) menyemak sama ada ( P ) membentuk laluan Hamiltonian, yang boleh dilakukan dalam masa polinomial berkenaan dengan saiz ( G ).
Konsep pengesahan masa polinomial adalah penting kerana ia menyediakan cara untuk mencirikan masalah yang boleh disemak dengan cekap, walaupun mencari penyelesaian mungkin tidak dapat dilaksanakan secara pengiraan. Ini membawa kepada soalan terkenal sama ada ( P = NP ), yang bertanya sama ada setiap masalah yang penyelesaiannya boleh disahkan dalam masa polinomial juga boleh diselesaikan dalam masa polinomial. Kelas ( P ) terdiri daripada masalah keputusan yang boleh diselesaikan dalam masa polinomial oleh mesin Turing yang menentukan. Jika ( P = NP ), ini bermakna setiap masalah dengan pengesah masa polinomial juga mempunyai penyelesai masa polinomial. Soalan ini kekal sebagai salah satu masalah terbuka yang paling penting dalam sains komputer.
Salah satu sifat utama NP ialah ia ditutup di bawah pengurangan masa polinomial. Pengurangan masa polinomial daripada bahasa ( L_1 ) kepada bahasa ( L_2 ) ialah fungsi pengiraan masa polinomial ( f ) supaya ( x dalam L_1 ) jika dan hanya jika ( f(x) dalam L_2 ). Jika wujud pengurangan masa polinomial daripada ( L_1 ) kepada ( L_2 ) dan ( L_2 ) adalah dalam NP, maka ( L_1 ) juga dalam NP. Sifat ini memainkan peranan penting dalam kajian NP-kelengkapan, yang mengenal pasti masalah "paling sukar" dalam NP. Masalah adalah NP-lengkap jika ia berada dalam NP dan setiap masalah dalam NP boleh dikurangkan kepadanya dalam masa polinomial. Masalah SAT adalah masalah pertama yang terbukti NP-lengkap, dan ia berfungsi sebagai asas untuk membuktikan NP-lengkap masalah lain.
Untuk menggambarkan dengan lebih lanjut konsep pengesahan masa polinomial, pertimbangkan masalah "Jumlah Subset". Masalah ini bertanya sama ada wujud subset set integer tertentu yang menjumlahkan kepada nilai sasaran yang ditentukan. Masalah Jumlah Subset adalah dalam NP kerana, diberikan satu set integer ( S ), nilai sasaran ( t ), dan subset ( S' ) daripada ( S ), seseorang boleh mengesahkan dalam masa polinomial sama ada jumlah unsur dalam ( S' ) sama dengan ( t ). Di sini, contoh ( x ) ialah pasangan ( (S, t) ), dan sijil ( y ) ialah subset ( S' ). Pengesah ( V ) menyemak sama ada jumlah unsur dalam ( S' ) sama dengan ( t ), yang boleh dilakukan dalam masa polinomial berkenaan dengan saiz ( S ).
Kepentingan pengesahan masa polinomial melangkaui pertimbangan teori. Dari segi praktikal, ia bermakna untuk masalah dalam NP, jika cadangan penyelesaian (sijil) disediakan, ia boleh disemak dengan cekap. Ini mempunyai implikasi yang ketara untuk protokol kriptografi, masalah pengoptimuman dan pelbagai bidang yang mengesahkan ketepatan penyelesaian adalah penting.
Untuk meringkaskan, kelas NP merangkumi masalah keputusan yang penyelesaian yang dicadangkan boleh disahkan dalam masa polinomial dengan algoritma penentu. Konsep ini adalah asas dalam teori kerumitan pengiraan dan mempunyai implikasi yang mendalam untuk kedua-dua aspek teori dan praktikal sains komputer. Kajian NP, pengesahan masa polinomial dan konsep berkaitan seperti kesempurnaan NP terus menjadi bidang penyelidikan yang rancak dan kritikal.
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 SAT menjadi masalah lengkap NP?
- Bolehkah masalah berada dalam kelas kerumitan NP jika terdapat mesin turing bukan deterministik yang akan menyelesaikannya dalam 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