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.ườ