Pengertian Kompleksitas NP: Pengertian dan Contohnya

NP adalah singkatan dari "Waktu Polinomial Nondeterministik". Ini adalah kelas kompleksitas yang mengacu pada jumlah waktu yang dibutuhkan untuk menyelesaikan suatu masalah. Pada NP, running time suatu algoritma bisa bersifat polinomial dalam ukuran inputnya, namun bisa juga bersifat nondeterministic, artinya running time bisa berbeda-beda tergantung pada solusi spesifik yang dipilih oleh algoritma tersebut.

Dengan kata lain, NP adalah sebuah kelas masalah yang dapat diselesaikan dalam waktu polinomial pada mesin non-deterministik. Mesin non-deterministik adalah mesin yang dapat mencoba semua solusi yang mungkin terhadap suatu masalah secara paralel, dan menerima solusi pertama yang berhasil. Hal ini memungkinkan mesin untuk memecahkan beberapa permasalahan jauh lebih cepat dibandingkan mesin deterministik, yang hanya dapat mencoba satu solusi dalam satu waktu.

Beberapa contoh permasalahan dalam NP meliputi:

* The traveling salesman problem (diberikan daftar kota dan jarak berpasangannya, temukan rute terpendek yang mengunjungi setiap kota tepat satu kali)
* Masalah knapsack (dengan mempertimbangkan sekumpulan item beserta bobot dan nilainya, tentukan subset item yang akan dimasukkan ke dalam knapsack dengan kapasitas terbatas yang memaksimalkan nilai total)
* Masalah kepuasan boolean (mengingat sekumpulan variabel boolean dan batasannya, tentukan apakah terdapat penetapan nilai pada variabel yang memenuhi semua batasan)

Kelas kompleksitas NP penting karena mencakup banyak masalah yang sulit diselesaikan dalam polinomial waktu, tetapi dapat diverifikasi dengan cepat oleh mesin deterministik. Artinya, meskipun suatu algoritma mungkin tidak dapat menemukan solusi dalam waktu polinomial, algoritma tersebut tetap berguna jika dapat memverifikasi solusi yang diusulkan dengan cepat.