16
Sebuah
kelas
yang
kompleks
dari decision
problems
di
mana
pada
dasarnya lebih sulit daripada masalah
yang
bias
diselesaikan
dengan
nondeterministic Turing machine dalam polynomial time.
Ada tiga kelas problem (permasalahan) :
•
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 dalam
co-NP adalah “no”
maka
ada pembuktian dari
fakta
itu
yang bisa dicek
dalam waktu polynomial.
Gambar 2.1 ilustrasi hubungan antara P, NP, co-NP.
2.4
Fungsi Heuristic
Pada
skripsi
ini,
pembahasan
difokuskan
pada
pemecahan
permasalah
untuk Dua
Dimension
Cutting
box, di
mana
tujuan
dari
pemecahan
masalah
ini
 |