Ch ng 3ươ : Ch ng minh các k t qu ứ ế ả
c a bài toán NP_đ y đủ ầ ủ
Gi ng viên :ả PSG.TSKH.Vũ Đình Hòa
I. Các khái ni mệ
1.1. L p bài toán P (polynomial time)ớ
1.2. L p bài toán NP(Nondeterministic polynomial ớ
time)
1.3. Quan h gi a l p P và l p NPệ ữ ớ ớ
II. Các bài toán NP_Complete
2.1. Phép d n v i th i gian đa th cẫ ớ ờ ứ
2.2. Bài toán NP_Complete (NPC)
2.3. M t s bài toán NPCộ ố
Ch ng 3ươ : Ch ng minh các k t qu c aứ ế ả ủ
bài toán NP_đ y đầ ủ
I. Các khái ni mệ
1.1. L p bài toán Pớ (polynomial time)
L p P là l p bài toán quy t đ nh gi i đ c ớ ớ ế ị ả ượ
trong th i gian đa th c trên máy Turing t t ờ ứ ấ
đ nh, hay l p nh ng bài toán d (có l i ị ớ ữ ễ ờ
gi i ch p nh n đ c).ả ấ ậ ượ
1.2. L p bài toán NPớ
Là l p bt quy t đ nh gi i đ c trong th i ớ ế ị ả ượ ờ
gian đa th c trên máy Turing không t t ứ ấ
đ nhị
1.3. Quan h gi a l p P và l p NPệ ữ ớ ớ
Ta có th th y m t cách tr c quan là Pể ấ ộ ự ⊆NP. Nh ng ư
chúng ta v n ch a bi t P=NP hay không, nh ng h u ẫ ư ế ư ầ
h t các nhà nghiên c u tin r ng Pế ứ ằ ≠NP là s t n t i ự ồ ạ
c a c a l p bt NPCủ ủ ớ
Dù chúng ta ch a bi t ch c ch n li u Pư ế ắ ắ ệ ≠NP song
vi c ch ra đ c m t bài toán là NPC ch ng t 1 s ệ ỉ ượ ộ ứ ỏ ự
th t là bt đó không th gi i đ c v ph ng di n tính ậ ể ả ượ ề ươ ệ
toán v i thu t toán chính xác, t t h n h t là l i gi i ớ ậ ố ơ ế ờ ả
theo thu t toán g n đúng.ậ ầ
Vi c xem xét quan h gi a P và NP d n đ n chúng ệ ệ ữ ẫ ế
ta đi đ n nghiên c u l p NPC ế ứ ớ
II. Các bài toán NP_Comlete (NPC)
2.1. Phép d n v i th i gian đa th cẫ ớ ờ ứ
Cho hai bài toán ∏1 và ∏2. Ta bi t r ngế ằ
22
11
2
1
NY
NY
πππ
πππ
∪=
∪=