20
Sebuah kelas yang kompleks dari decision problems
di mana pada dasarnya
lebih sulit dari pada masalah yang biasa diselesaikan dengan non-deterministic turing
machine dalam polynomial time. Terdapat tiga kelas permasalahan(problem), yaitu :
P adalah kumpulan “yes/no” problem yang bisa dipecahkan dalam waktu
polynomial. Jadi bisa dikatakan bahwa P adalah kumpulan permasalahan
yang bisa dipecahkan secara cepat.
NP adalah sekumpulan “yes/no” problem diikuti dengan property
: jika
“yes”
maka ada pembuktian dari fakta itu yang bisa dicek dalam waktu
polynomial. Jadi bisa dikatakan bahwa NP adalah sekumpulan
permasalahan di mana bisa dikatakan “yes”, jika terdapat solusinya.
Co-NP adalah kebalikan dari NP, jika jawaban dari permasalahan co-NP
adalah “no” maka ada pembuktian dari fakta itu yang bisa dicek dalam
waktu polynomial.
Gambar 2.2 Hubungan antara P, NP, dan co-NP
2.7
Metode Pencarian Heuristic
Menurut Munir (2009), heuristic
berasal dari sebuah kata kerja Yunani,
heuriskein
yang berarti mencari atau menemukan. Dalam dunia pemrograman,
sebagian orang menggunakan kata heuristic
sebagai lawan kata dari algoritmik,
dimana kata heuristic
ini diartikan sebagai proses yang mungkin dapat
 |