DAA - Kelas P & NP
Dalam Ilmu Komputer, banyak masalah yang diselesaikan yang tujuannya untuk memaksimalkan atau meminimalkan beberapa nilai, sedangkan di masalah lain kami mencoba mencari solusi atau tidak. Oleh karena itu, masalahnya dapat dikategorikan sebagai berikut -
Masalah pengoptimalan
Masalah pengoptimalan adalah masalah yang tujuannya adalah untuk memaksimalkan atau meminimalkan beberapa nilai. Sebagai contoh,
Menemukan jumlah warna minimum yang diperlukan untuk mewarnai grafik tertentu.
Menemukan jalur terpendek antara dua simpul dalam sebuah grafik.
Masalah Keputusan
Ada banyak masalah yang jawabannya adalah Ya atau Tidak. Jenis masalah ini dikenal sebagai decision problems. Sebagai contoh,
Apakah grafik tertentu dapat diwarnai hanya dengan 4 warna.
Menemukan siklus Hamiltonian dalam grafik bukanlah masalah keputusan, sedangkan memeriksa grafik adalah Hamiltonian atau bukan merupakan masalah keputusan.
Apa itu Bahasa?
Setiap masalah keputusan hanya dapat memiliki dua jawaban, ya atau tidak. Oleh karena itu, masalah keputusan mungkin menjadi milik suatu bahasa jika memberikan jawaban 'ya' untuk input tertentu. Bahasa adalah totalitas masukan yang jawabannya adalah Ya. Sebagian besar algoritme yang dibahas di bab sebelumnya adalahpolynomial time algorithms.
Untuk ukuran masukan n, jika kompleksitas waktu kasus terburuk dari suatu algoritme adalah O(nk), dimana k adalah suatu konstanta, algoritme tersebut adalah algoritme waktu polinomial.
Algoritma seperti Perkalian Rantai Matriks, Jalur Terpendek Sumber Tunggal, Jalur Terpendek Semua Pasangan, Pohon Rentang Minimum, dll. Berjalan dalam waktu polinomial. Namun ada banyak masalah, seperti penjual keliling, pewarnaan grafik yang optimal, siklus Hamiltonian, menemukan jalur terpanjang dalam grafik, dan memenuhi rumus Boolean, yang tidak diketahui algoritme waktu polinomialnya. Masalah ini termasuk dalam kelas masalah yang menarik, yang disebutNP-Complete masalah, yang statusnya tidak diketahui.
Dalam konteks ini, kita dapat mengkategorikan masalah sebagai berikut -
Kelas-P
Kelas P terdiri dari masalah-masalah yang dapat diselesaikan dalam waktu polinomial, yaitu masalah-masalah ini dapat diselesaikan dalam waktu O(nk) dalam kasus terburuk, di mana k konstan.
Masalah ini disebut tractable, sementara yang lain dipanggil intractable or superpolynomial.
Secara formal, algoritme adalah algoritme waktu polinomial, jika terdapat polinomial p(n) sedemikian rupa sehingga algoritme dapat menyelesaikan contoh ukuran apa pun n pada suatu waktu O(p(n)).
Masalah yang membutuhkan Ω(n50) waktu untuk menyelesaikan pada dasarnya sulit untuk besar n. Algoritme waktu polinomial yang paling dikenal berjalan dalam waktuO(nk) untuk nilai yang cukup rendah k.
Keuntungan dalam mempertimbangkan kelas algoritma waktu polinomial adalah semua itu masuk akal deterministic single processor model of computation dapat disimulasikan satu sama lain dengan paling banyak lambat polinomial-d
NP-Class
NP kelas terdiri dari masalah-masalah yang dapat diverifikasi dalam waktu polinomial. NP adalah kelas masalah keputusan yang mudah untuk memeriksa kebenaran jawaban yang diklaim, dengan bantuan sedikit informasi tambahan. Oleh karena itu, kami tidak meminta cara untuk menemukan solusi, tetapi hanya untuk memverifikasi bahwa solusi yang dituduhkan benar-benar tepat.
Setiap masalah di kelas ini dapat diselesaikan dalam waktu eksponensial menggunakan pencarian lengkap.
P versus NP
Setiap masalah keputusan yang dapat diselesaikan dengan algoritma waktu polinomial deterministik juga dapat diselesaikan dengan algoritma non-deterministik waktu polinomial.
Semua masalah di P dapat diselesaikan dengan algoritma waktu polinomial, sedangkan semua masalah di NP - P tidak bisa dipecahkan .
Tidak diketahui apakah P = NP. Namun banyak masalah yang diketahui dalam NP dengan sifat bahwa jika termasuk dalam P, maka dapat dibuktikan bahwa P = NP.
Jika P ≠ NP, ada masalah di NP yang bukan di P maupun di NP-Complete.
Masalahnya milik kelas Pjika mudah menemukan solusi untuk masalah tersebut. Masalahnya milikNP, jika mudah untuk memeriksa solusi yang mungkin sangat membosankan untuk ditemukan.