Dalam teori kompleksitas komputasi (computational complexity theory), NP (nondeterministic polynomial time) adalah kelas kompleksitas yang digunakan untuk mengklasifikasikan masalah keputusan. NP Problems adalah himpunan persoalan keputusan yang dapat diselesaikan oleh algoritma non-deterministik dalam waktu polinom. Kebanyakan persoalan keputusan adalah NP
Sebelumnya, untuk lebih mempermudah, kita gunakan analgi untuk menggambarkan kelas-kelas kompleksitas suatu masalah.
P Problems merupakan permasalahan yang Anda tahu dapat Anda pecahkan dengan mudah. Apakah Anda lebih suka bakso atau gado-gado? Mungkin Anda perlu 1 menit untuk menjawabnya, kadang-kadang Anda mungkin butuh waktu lebih lama untuk memutuskan apakah memilih bakso atau gado-gado. Tetapi itu tidak masalah, karena pada akhirnya anda akan mengambil keputusan.
NP problems adalah permasalahan yang lebih kompleks dibandingkan P Problems. Misalnya, Dapatkah Anda menemukan teman yang lebih pendek dari Anda, tetapi lebih tinggi dari saudara perempuan Anda? Anda mungkin menjawab, Bisa
Tetapi jika pertanyaannya dirubah : Dapatkah Anda menemukan orang yang lebih pendek 5 cm dari Anda , tetapi lebih tinggi dari 3 cm dari kakak Anda, Anda mungkin menjawab tidak bisa.
Padahal belum tentu kamu tidak bisa menemukan orang dengan kriteria seperti itu.
NP Complete, adalah NP problems dengan peringatan tambahan yang menanyakan apakah kita dapat mengurangi masalah tersebut menjadi masalah NP complete lainnya? Apakah anda bisa merubah masalah X menjadi masalah Y
NP Hard adalah masalah yang lebih sulit atau sama dengan masalah NP Complete. Beberapa referensi mengatakan bahwa NP Hard adalah masalah yang tidak ada solusinya.
Gambar Hubungan anatara P, NP, NP Complete dan NP Hard
Polynomial Problem (P Problems) merupakan problem di mana waktu yang dibutuhkan untuk menghasilkan solusinya terbatas pada waktu polynomial dalam tingkat kecil
Contohnya adalah seperti permasalahan evaluasi polynomial dengan O(n) , pengurutan (sorting) dengan O(n log n) dan string editing dengan O(mn).
Non Polynomial Problem (NP Problems) merupakan permasalahan yang dalam pencarian solusinya, tidak ada satupun yang dapat mengembangkan algoritma (solusi) dengan waktu polynomial. Hal ini sangat penting karena algoritma yang waktu pencarian solusinya lebih besar dari polynomial (biasanya waktu pencarian adalah eksponensial) membutuhkan waktu yang cukup lama untuk menjalankan problem skala menengah. (Horowitz, Sahni dan Rajasekaran, 1998).
Contohnya adalah seperti permasalahan traveling sales person dengan O(n22n) dan permasalahan Knapsack dengan O(2n/2).
Algoritma Non Polynomial (NP) dibagi menjadi dua kelas yaitu NP-hard dan NP-complete.
Suatu problem yang termasuk kedalam NP-complete jika memiliki sifat dapat dipecahkan dalam waktu polynomial jika dan hanya jika seluruh problem NP-complete juga dapat dipecahkan dalam waktu polynomial.
Jika sebuah problem NP-hard dapat dipecahkan dalam waktu polynomial maka seluruh problem NP-complete dapat dipecahkan dalam waktu polynomial.
Seluruh problem NP-complete merupakan problem NP-hard , tetapi sebagian problem NP-hard belum tentu menjadi problem NP-complete (Horowitz, Sahni dan Rajasekaran, 1998)