13.11.2004 Ch. 12: NP-Completeness 1
NP-Đy Đầ ủ
13.11.2004 Ch. 12: NP-Completeness 2
Vài khái ni m c b nệ ơ ả
ªBài toán
–các tham số
–các tính ch t mà l i gi i c n ph i th a mãnấ ờ ả ầ ả ỏ
ªM t th c th (instance) c a bài toán là bài toán mà các tham s có tr ộ ự ể ủ ố ị
c thụ ể.
13.11.2004 Ch. 12: NP-Completeness 3
Hình th c hóa khái ni m bài toánứ ệ
ªVí d : bài toán SHORTEST-PATH làụ
–“không hình th c”: bài toán tìm đng đi ng n nh t gi a hai ứ ườ ắ ấ ữ
đnh cho tr c trong m t đ th vô h ng, không có tr ng s ỉ ướ ộ ồ ị ướ ọ ố G
= (V, E).
–“hình th c”:ứ
°M t ộth c thự ể c a bài toán là m t c p ba g m m t đ th c ủ ộ ặ ồ ộ ồ ị ụ
th và hai đnh c th .ể ỉ ụ ể
°M t ộl i gi iờ ả là m t dãy các đnh c a đ th .ộ ỉ ủ ồ ị
°Bài toán SHORTEST-PATH là quan h k t h p m i th c ệ ế ợ ỗ ự
th g m m t đ th và hai đnh v i m t đng đi ng n nh t ể ồ ộ ồ ị ỉ ớ ộ ườ ắ ấ
(n u có) trong đ th n i hai đnh:ế ồ ị ố ỉ
SHORTEST-PATH I S
13.11.2004 Ch. 12: NP-Completeness 4
Bài toán tr u t ngừ ượ
ªĐnh nghĩa: m t ị ộ bài toán tr u t ngừ ượ Q là m t quan h nh phân trên ộ ệ ị
m t t p ộ ậ I, đc g i là t p các ượ ọ ậ th c thự ể (instances) c a bài toán, và ủ
m t t p ộ ậ S, đc g i là t p các ượ ọ ậ l i gi iờ ả c a bài toán:ủ
Q I S
13.11.2004 Ch. 12: NP-Completeness 5
Bài toán quy t đnhế ị
ªM tộ bài toán quy t đnhế ị Q là m t ộbài toán tr u t ngừ ượ mà quan h ệ
nh phân ịQ là m t ộhàm t ừI đn ếS = {0, 1}, 0 t ng ng v i “no”, 1 ươ ứ ớ
t ng ng v i “yes”.ươ ứ ớ
ªVí d : bài toán quy t đnh PATH làụ ế ị
Cho m t đ th ộồịG = (V, E), hai đnh ỉu, v V, và m t s nguyên ộ ố
d ng ươ k.
Đt ặi = G, u, v, k, m t th c th c a bài toán quy t đnh PATH,ộ ự ể ủ ế ị
–PATH(i) = 1 (yes) n u t n t i m t đng đi gi a ế ồ ạ ộ ườ ữ u và v có chi u ề
dài k
–PATH(i) = 0 (no) trong các tr ng h p khác.ườ ợ