13.11.2004 Ch. 12: NP-Completeness 1
NP-Ñaày Ñuû
13.11.2004 Ch. 12: NP-Completeness 2
Vaøi khaùi nieäm cô baûn
ªBaøi toaùn
–caùc tham soá
–caùc tính chaát maø lôøi giaûi caàn phaûi thoûa maõn
ªMoät thöïc theå (instance) cuûa baøi toaùn laø baøi toaùn maø caùc tham soá coù
trò cuï theå.
13.11.2004 Ch. 12: NP-Completeness 3
Hình thöùc hoùa khaùi nieäm baøi toaùn
ªVí duï: baøi toaùn SHORTEST-PATH laø
– “khoâng hình thöùc”: baøi toaùn tìm ñöôøng ñi ngaén nhaát giöõa hai
ñænh cho tröôùc trong moät ñoà thò voâ höôùng, khoâng coù troïng soá G=
(V, E).
– “hình thöùc”:
°Moät thöïc theå cuûa baøi toaùn laø moät caëp ba goàm moät ñoà thò cuï
theå vaø hai ñænh cuï theå.
°Moät lôøi giaûi laø moät daõy caùc ñænh cuûa ñoà thò .
°Baøi toaùn SHORTEST-PATH laø quan heä keát hôïp moãi thöïc
theå goàm moät ñoà thò vaø hai ñænh vôùi moät ñöôøng ñi ngaén nhaát
(neáu coù) trong ñoà thò noái hai ñænh:
SHORTEST-PATH IS
13.11.2004 Ch. 12: NP-Completeness 4
Baøi toaùn tröøu töôïng
ªÑònh nghóa: moät baøi toaùn tröøu töôïng Qlaø moät quan heä nhò phaân treân
moät taäp I, ñöôïc goïi laø taäp caùc thöïc theå (instances) cuûa baøi toaùn, vaø
moät taäp S, ñöôïc goïi laø taäp caùc lôøi giaûi cuûa baøi toaùn:
QIS
13.11.2004 Ch. 12: NP-Completeness 5
Baøi toaùn quyeát ñònh
ªMoät baøi toaùn quyeát ñònh Qlaø moät baøi toaùn tröøu töôïng maø quan heä
nhò phaân Qlaø moät haøm töø Iñeán S= {0, 1}, 0 töông öùng vôùi “no”, 1
töông öùng vôùi “yes”.
ªVí duï: baøi toaùn quyeát ñònh PATH laø
Cho moät ñoà thò G= (V, E), hai ñænh u, vV, vaø moät soá nguyeân
döông k.
Ñaët i= G, u, v, k, moät thöïc theå cuûa baøi toaùn quyeát ñònh PATH,
–PATH(i) = 1 (yes) neáu toàn taïi moät ñöôøng ñi giöõa uvaø vcoù chieàu
daøi k
–PATH(i) = 0 (no) trong caùc tröôøng hôïp khaùc.