Memahami Kerumitan NP: Definisi dan Contoh

NP bermaksud "Masa Polinomial Tidak Tentu". Ia adalah kelas kerumitan yang merujuk kepada jumlah masa yang diperlukan untuk menyelesaikan masalah. Dalam NP, masa berjalan algoritma boleh menjadi polinomial dalam saiz input, tetapi ia juga boleh menjadi tidak tentu, bermakna masa berjalan boleh berbeza-beza bergantung pada penyelesaian khusus yang dipilih oleh algoritma.

Dalam erti kata lain, NP ialah kelas masalah yang boleh diselesaikan dalam masa polinomial pada mesin bukan penentu. Mesin bukan deterministik ialah mesin yang boleh mencuba semua penyelesaian yang mungkin untuk masalah secara selari, dan menerima yang pertama yang berfungsi. Ini membolehkan mesin menyelesaikan beberapa masalah dengan lebih pantas daripada mesin deterministik, yang hanya boleh mencuba satu penyelesaian pada satu masa.

Beberapa contoh masalah dalam NP termasuk:

* Masalah jurujual perjalanan (diberi senarai bandar dan jarak berpasangan mereka, cari laluan terpendek mungkin yang melawati setiap bandar tepat sekali)
* Masalah ransel (diberi set item dan berat serta nilainya, tentukan subset item untuk dimasukkan ke dalam beg beg berkapasiti terhad yang memaksimumkan jumlah nilai)
* Masalah kepuasan boolean (memandangkan satu set pembolehubah boolean dan kekangannya, tentukan sama ada wujud penetapan nilai kepada pembolehubah yang memenuhi semua kekangan)

Kelas kerumitan NP adalah penting kerana ia merangkumi banyak masalah yang sukar diselesaikan dalam polinomial masa, tetapi boleh disahkan dengan cepat oleh mesin penentu. Ini bermakna walaupun algoritma mungkin tidak dapat mencari penyelesaian dalam masa polinomial, ia masih boleh berguna jika ia boleh mengesahkan penyelesaian yang dicadangkan dengan cepat.