Ế Ộ Ứ Ạ
Ề
CHUYÊN Đ : LÝ THUY T Đ PH C T P THU T TOÁN
Ậ
LÝ THUY T NP - Đ Y Đ Ầ Ế Ủ
Giáo viên : Th y Vũ Đình Hoà ầ
The theory of NP-Completeness
1
(THE THEORY OF NP - COMPLETENESS)
N I DUNG
Ộ
1. Bài toán quy t đ nh ế ị
2. Ngôn ng và l c đ mã hóa ữ ượ ồ
3. Máy Turing t t đ nh và l p P ấ ị ớ
4. Tính toán không t t đ nh và l p NP ấ ị ớ
5. M i quan h gi a l p P và l p NP ệ ữ ớ ố ớ
6. Phép d n th i gian đa th c và l p NPC ứ ẫ ờ ớ
The theory of NP-Completeness
2
7. Thuy t Cook ế
1. BÀI TOÁN QUY T Đ NH
Ế
Ị
Bài toán quy t đ nh (Decision Problem - DP) là bài toán ế ị
ch có câu tr l i là có ho c không (hay còn g i là tr l i ả ờ ỉ ả ờ ặ ọ
nh phân). ị
M i th hi n c a bài toán nghĩa là m i tr ể ệ ỗ ườ ủ ỗ ng h p cá ợ
bi t c a bài toán có m t tr l i. ệ ủ ộ ả ờ
M t bài toán quy t đ nh ∏ đ n gi n bao g m m t t p ộ ậ ế ị ộ ơ ồ
∏ các th hi n và t p con Y
h p Dợ ể ệ ậ ể ệ D∏ là các th hi n ả ∏ ˝
The theory of NP-Completeness
3
đúng
1. BÀI TOÁN QUY T Đ NH
Ế
Ị
Instance: …
Question:…
M t bài toán quy t đ nh phát bi u d i d ng: ế ị ể ướ ạ ộ
Instance: Cho 2 đ th G
ồ ị
1 = (V1, E1) và G2 = (V2, E2)
Question: đ th G
Ví d 1: bài toán s đ ng c u c a đ th con ự ẳ ấ ủ ồ ị ụ
1 có ch a m t đ th con G
1’ mà G1’
ồ ị ộ ồ ị ứ
2 hay không?
The theory of NP-Completeness
4
đ ng c u v i đ th G ấ ớ ồ ị ẳ
1. BÀI TOÁN QUY T Đ NH
Ế
Ị
Gi ả i thích v đ th đ ng c u: ề ồ ị ẳ ấ
1’| = |V2|, |E1’| = |E2| và
ư ế ẳ ấ G1’ đ ng c u v i G ớ 2 n u nh có |V
2 V1’ sao cho {u,v} ˛
đó t n t i m t song ánh f : V ở ồ ạ ộ
The theory of NP-Completeness
5
˛ ỉ E2 khi và ch khi {f(u), f(v)} E1’).
1. BÀI TOÁN QUY T Đ NH
Ế
Ị
Instance: T p h u h n các thành ph : C = {c ạ
ữ
ậ
ố
1, c2,…
ố i, cj là d(ci, cj) ˛
Z+.
cm}, kho ng cách gi a hai thành ph c ữ ả ộ ố ˛ Z+, m t s B
Question: t n t
i hay không m t đ
ng đi nào qua t
t
ồ ạ
ộ ườ
ấ
ố
ớ
)2(
Ví d 2: Traveling Salesman ụ
h n B? (T n t ơ 1
m
+
-
c các thành ph trong C mà có t ng đ dài không l n ả C p )1( i m t s p th t ứ ự ộ ắ ồ ạ ( Cd , )) ( Cd C
ộ ổ C mC ,..., , p p ( ) sao B
C
(
)
,
p
p
p
p
cho
)( i
+ )1( i
(
m
)
)1(
= 1
i
)
The theory of NP-Completeness
6
£ (cid:229)
1. BÀI TOÁN QUY T Đ NH
Ế
Ị
M t bài toán quy t đ nh có th đ m t ế ị ể ượ ộ c chuy n hoá t ể ừ ộ
bài toán t i u. ố ư
i u là “ tìm m t đ ng đi có đ dài ố ư ộ ườ ộ
nh nh t trong s t t c các đ ng đi n i 2 đ nh đ th Ví d :ụ Bài toán t ấ ỏ ố ấ ả ườ ồ ị” ố ỉ
↔ BTQĐ : thêm vào m t tham s B và h i xem có ộ ố ỏ
đ ≤ B hay không? ườ ng đi nào có đ dài L mà L ộ
V i đi u ki n là hàm chi phí ph i t ả ươ ề ệ ớ ng đ i d đánh ố ễ
giá, bài toán quy t đ nh có th không khó khăn h n bài ế ị ể ơ
The theory of NP-Completeness
7
toán t i u t ng ng ố ư ươ ứ
1. BÀI TOÁN QUY T Đ NH
Ế
Ị
N u tìm th y m t đ ng đi có đ dài nh nh t cho bài ộ ườ ế ấ ấ ộ ỏ
toán TS theo th i gian đa th c, cũng có th gi i quy t ể ả ứ ờ ế
bài toán quy t đ nh đ ế ị ượ ế ợ c k t h p theo th i gian đa th c. ờ ứ
Lý thuy t NP đ y đ gi i h n là ch chú ý t i các bài ủ ớ ạ ế ầ ỉ ớ
toán quy t đ nh nh ng cũng có th m r ng s liên quan ể ở ộ ế ị ự ư
i các bài toán t i u. c a thuy t NP đ y đ t ủ ầ ủ ớ ế ố ư
Nguyên nhân c a s gi i h n này là các DPs có m t b n ủ ự ớ ạ ộ ả
The theory of NP-Completeness
8
sao r t t nhiên và nó đ ấ ự ượ ọ c g i là ngôn ng . ữ
2. NGÔN NG VÀ L
C Đ MÃ HÓA
Ữ
ƯỢ Ồ
các kí hi u, chúng ta có
ớ ấ
ệ
th bi u di n
t c các xâu h u h n các
ể ể
ợ ấ ả
ữ ạ
ộ ậ ữ ạ (cid:229) V i b t kì m t t p h u h n ễ (cid:229) * là t p h p t ậ .
kí hi u l y t
ệ ấ ừ ậ (cid:229) t p
N u L là m t t p con c a
ộ ậ
ế
ằ
.
ủ (cid:229) m t ngôn ngôn ng trên t p các ch cái c a
ữ
ữ
ộ
ủ (cid:229) *, chúng ta nói r ng L là ậ
The theory of NP-Completeness
9
Đ nh nghĩa ngôn ng : ữ ị
2. NGÔN NG VÀ L
C Đ MÃ HÓA
Ữ
ƯỢ Ồ
= {0, 1}, khi đó I* = {ε, 0, 1, 01, 10, 11, 000, 001,… } Ví d :ụ N u ế (cid:229)
Khi đó {01,001,111,1101010} là m t ngôn ng trên t p {0,1} ữ ậ ộ
ng ng gi a bài toán quy t đ nh và ngôn ng đ c S t ế ị ữ ượ
c đ mã hoá. ữ ượ ồ
ự ươ ứ d n đ n b i các l ẫ ế ở M t l ấ
ộ ợ ộ
The theory of NP-Completeness
10
c đ mã hoá e cho bài toán ∏ cung c p m t cách ồ ộ ượ m i s ki n c a ∏ b ng m t xâu thích h p các th c miêu t ằ ả ỗ ự ệ ủ ứ ký hi u trên t p ch cái c đ nh ∑. ố ị ữ ậ ệ
2. NGÔN NG VÀ L
C Đ MÃ HÓA
Ữ
ƯỢ Ồ
Bài toán ∏ và l
c đ mã hoá e cho ∏ chia
ượ ồ
1. Nh ng xâu không mã hoá các bi u hi n c a ∏.
ệ ủ
ữ
ể
2. Nh ng xâu mã hoá các bi u hi n c a ∏ mà trên đó câu tr
ệ ủ
ữ
ể
ả
l
i là No.
ờ
3. Nh ng xâu mã hoá các bi u hi n c a ∏ mà trên đó câu tr
ệ ủ
ữ
ể
ả
l
i là Yes.
ờ
∑* thành 3 l p:ớ
Ngôn ng : L[∏, e] = {x
đ
c s d ng b i e, và x
ữ
ượ ử ụ
ở
˛
mã hóa m t th hi n I ộ
ể ệ
(cid:229) * v i ớ (cid:229) Yp b ng e} ằ
The theory of NP-Completeness
11
˛
2. NGÔN NG VÀ L
C Đ MÃ HÓA
Ữ
ƯỢ Ồ
M t l c đ mã hoá h p lý ph i đ m b o 2 tính năng ộ ượ ả ả ả ồ ợ
ng h p c a bài toán nên
ắ
ọ
ườ
ủ
ợ
“Tính ng n g n” là các tr v i s khúc chi
c mô t
đ
t m t cách t
nhiên.
ả ớ ự
ượ
ế
ộ
ự
“Kh năng gi ả
ả
i mã” là đ a ra b t kì m t thành ph n c ầ ụ
ư
ấ
ộ
ng h p chung, thì l
th nào c a m t tr ủ
ộ ườ
ể
ợ
ượ ồ
c đ có kh ả
năng ch rõ m t thu t toán có th i gian đa th c.
ứ
ậ
ộ
ờ
ỉ
The theory of NP-Completeness
12
là : “tính ng n g n” và có “kh năng gi i mã”. ắ ọ ả ả
2. NGÔN NG VÀ L
C Đ MÃ HÓA
Ữ
ƯỢ Ồ
Đ nh nghĩa m t l c đ mã hoá chu n: ộ ượ ồ ẩ ị
L c đ mã hoá chu n ượ ẩ s ánh x các th hi n sang các ể ệ ẽ ạ ồ
xâu có c u trúc trên tâp ch cái ψ = {0, 1, -, [,], (, ), …}. ữ ấ
The theory of NP-Completeness
13
Đ nh nghĩa xâu c u trúc m t cách đ quy nh sau: ư ệ ấ ộ ị
2. NGÔN NG VÀ L
C Đ MÃ HÓA
Ữ
ƯỢ Ồ
Bi u di n nh phân c a m t s nguyên k (g m các ch ữ
ộ ố
ủ
ể
ễ
ồ
ị
c là d u - n u k là s âm) là m t
s 0 và 1), (đ ng tr ố
ằ
ướ
ế
ấ
ố
ộ
xâu có c u trúc bi u di n s nguyên k. ể
ễ ố
ấ
ế
ễ ố
ể
ấ
ộ
N u x là m t xâu có c u trúc bi u di n s nguyên k, c s d ng
khi đó [x] là m t xâu có c u trúc có th đ
ể ượ ử ụ
ấ
ộ
nh m t “tên” (name) .
ư ộ
N u xế
ể
ễ
ấ
1, x2, ..., xm là các xâu có c u trúc bi u di n các
ng X
đ i t ố ượ
ộ
1,X2, …, Xm, khi đó (x1, …, xm) là m t xâu
ấ
ễ
ỗ
1,…,Xm)
có c u trúc bi u di n chu i (X ể The theory of NP-Completeness
14
2. NGÔN NG VÀ L
C Đ MÃ HÓA
Ữ
ƯỢ Ồ
M t t p các đ i t
ng đ
các
ộ ậ
ố ượ
ượ
c bi u di n b i th t ễ
ứ ự
ể
ở
ph n t
ầ ử ủ
c a nó nh m t chu i ỗ 1, …, Xm> và xem nh là ư xâu có c u trúc t
ấ ươ ứ ng ng v i chu i đó.
ớ ỗ M t đ th v i t p đ nh là V và t p c nh là E đ
ỉ ộ ồ ị ớ ậ ạ ậ ượ c bi u
ể di n b i m t xâu có c u trúc (x, y), ễ ấ ở ộ ở đó x là m t xâu có
ộ c u trúc bi u di n t p V và y là xâu có c u trúc bi u di n
ấ ễ ậ ể ể ễ ấ c a E …) t p E (các ph n t
ậ ầ ử ủ The theory of NP-Completeness 15 Các bi u di n cho 4 ki u đ i t
ễ ố ượ ể ể ng nh sau:
ư M t hàm h u h n f : {U
ữ ạ ộ ượ c bi u
ể 1, U2,…, Um} → W đ di n b i m t xâu có c u trúc {(x ễ ấ ở ộ ở 1, y1), …, (xm, ym)} ể ễ i và yi là xâu có c u ấ trúc bi u di n f(U W, 1 ≤ i ≤ m. ể ễ đó xi là xâu có c u trúc bi u di n U
ấ
i) ˛ c bi u di n b i m t xâu có c u M t s h u t q đ
ộ ố ữ ỉ ượ ể ễ ấ ở ộ trúc (x, y) ở đó x là xâu có c u trúc bi u di n m t s
ộ ố ể ễ ấ nguyên a, y là xâu bi u di n m t s nguyên b và đó ộ ố ễ ể ở a / b = q, và ướ c chung l n nh t c a a và b là 1.
ấ ủ ớ The theory of NP-Completeness 16 3.1. Miêu t máy Turing t t đ nh (DTM) ả ấ ị Máy Turing t ấ ị t đ nh g m có:
ồ 1. Con tr đi u khi n tr ng thái ỏ ề ể ạ 2. M t đ u đ c ghi ộ ầ ọ 3. M t băng vô h n n m ngang v i các ô vuông. D i ướ ạ ằ ộ ớ The theory of NP-Completeness 17 các ô vuông có đánh các nhãn là:… -3, -2, -1, 0, 1, 2, 3… B đi u khi n
ể
ộ ề
tr ng thái
ạ
h u h n
ữ ạ Đ u đ c ghi
ọ ầ Băng vô h nạ 3.1. Miêu t máy Turing t t đ nh ả ấ ị The theory of NP-Completeness 18 3.1. Miêu t máy Turing t t đ nh ả ấ ị ng trình cho m t DTM g m các thông tin: M t ch
ộ ươ ồ ộ (cid:204) ộ ậ ộ ậ ữ ợ ồ (cid:229) M t t p h p T nh ng kí hi u, bao g m m t t p con
ệ
T \ (cid:229) tr ng b . T và m t kí t
ộ ự ắ M t t p h p Q các tr ng thái, bao g m tr ng thái b t đ u ắ ầ ộ ậ ạ ạ ợ ồ ế ạ qo và hai tr ng thái k t thúc là q Y và qN. M t hàm chuy n tr ng thái ể ạ ộ ? : (Q - {qY, qN}) * T → Q * T * {-1, +1,0} The theory of NP-Completeness 19 ˛ 3.1. Miêu t máy Turing t t đ nh ả ấ ị d cho phép v i m i tr ng thái c a Hàm chuy n tr ng thái:
ể ạ ỗ ạ ủ ớ máy và m t kí ki u đ c đ ô tr ng đ i di n, ta xác ệ ộ ọ c t
ượ ừ ệ ố ố Tr ng thái ti p theo. ế ạ Kí hi u s đ c vi ệ ẽ ượ ế t lên băng đè lên kí hi u v a đ c
ệ ừ ọ H ng d ch chuy n c a đ u đ c
ọ ể ủ ầ ướ ị The theory of NP-Completeness 20 c: đ nh đ
ị ượ 3.1. Miêu t máy Turing t t đ nh ả ấ ị 1. Xâu x đ c đ t lên băng, m i kí t c đ t vào m i ô. ượ ặ ỗ đ
ự ượ ặ ỗ T t c các ô còn l i đ u ch a kí t tr ng. Ch ng trình ấ ả ạ ề ứ ự ắ ươ ô b t đ u v i tr ng thái ban đ u là q
ắ ầ ầ ạ ớ ớ ầ ọ ở 0, v i đ u đ c ch a kí t đ u tiên c a xâu ứ ự ầ ủ 2. Các b c tính toán: … ướ The theory of NP-Completeness 21 Quá trình th c hi n c a DTM
ự ệ ủ 2.1. Miêu t máy Turing t t đ nh ả ấ ị 2. Các b c tính toán: … ướ - Đ c kí t
ọ ự ố đ i di n v i đ u đ c
ọ
ệ ớ ầ Quá trình th c hi n c a DTM
ự ệ ủ - Thay kí hi u đó b ng kí hi u tính t hàm ệ ệ ằ ừ - D i đ u đ c theo h ờ ầ ọ ướ ng c a hàm d ch chuy n
ể ủ ị - Đ i tr ng thái hi n t i thành tr ng thái c a hàm d ch ệ ạ ạ ổ ủ ạ ị chuy n. ể The theory of NP-Completeness 22 d 3.1. Miêu t máy Turing t t đ nh ả ấ ị Quá trình th c hi n c a DTM
ự ệ ủ Xâu x đ c th a nh n khi quá trình th c hi n đ t đ n ượ ạ ế ự ừ ệ ậ The theory of NP-Completeness 23 tr ng thái th a nh n. ừ ậ ạ 3.2. Ví d ụ Cho các t p h p sau: ậ ợ T = {0, 1, b}, (cid:229) = {0, 1} Q = {q0, q1, q2, q3, qY, qN} Cho xâu vào: The theory of NP-Completeness 24 x = “10100” The theory of NP-Completeness 25 Hàm tr ng thái cho trong b ng: ả ạ The theory of NP-Completeness 26 t đ nh không có quá trình vô Cho M là m t máy Turing t
ộ ấ ị c đ nh h n. Hàm ph c t p theo th i gian c a M là hàm đ
ạ ứ ạ ủ ờ ượ ị TM : Z+ → Z+ nghĩa nh sau: ư (cid:229) *, v i |x| = n, quá trình TM (n) = max {m: có m t x ộ ớ th c hi n c a M trên đ u vào x chi m th i gian là m}. ệ ủ ự ế ầ ờ The theory of NP-Completeness 27 ˛ M t máy Turing M đ ộ c g i là đa th c n u nh t n
ứ ư ồ ế Z+ TM(n) ≤ p(n). t
ạ i m t đa th c P cho t
ứ ộ ọ
ượ
ấ ả ˛
t c n : L p P là m t l p các bài toán quy t đ nh ị ộ ớ ế ị ớ gi c b i máy Turing t t đ nh trong th i gian đa Đ nh nghĩa
i đ
ả ượ ở ấ ị ờ th cứ M t hàm tính v i th i gian đa th c, n u có m t máy ứ ế ộ ớ ộ ờ The theory of NP-Completeness 28 Turring đa th c tính nó. ứ Máy Turing không t t đ nh: ấ ị ˛ S S q0 Ngôn ng đoán nh n b i NDTM: ậ ở ữ M i t x đ c ch p nh n b i máy Turing b t đ nh M ỗ ừ ượ ấ ị ậ ấ ở n u xu t phát v i input x, máy Turing b t đ nh M
ế ấ ấ ớ ị chuy n đ n tr ng thái q ế ể ạ Y.
0*œ M ch p nh n w} g i là ngôn
ậ S Kí hi u là L ấ ọ ệ M = {w˛
ậ ượ ở ng đoán nh n đ c b i máy NDTM ữ Th i gian tính toán c a NDTM: Đ c tính là th i gian t i ượ ủ ờ ờ ố M(x)=
i sau t ọ ể ủ ậ ấ ừ ấ ậ ạ c} thi u c a m i quá trình tính toán ch p nh n x, nghĩa là t
min{tœ có quá trình tính toán ch p nh n Input x d ng l
b
ướ Đ ph c t p th i gian (th i gian tính) c a máy NDTM, kí
ờ ứ ạ ủ ộ ờ M(n) cũng ch xét trên các t
ỉ hi u là T c đ nh nghĩa ệ ượ ị ừ ˛
x LM đ nh sau:
ư TM(n)= max{tœ x˛ LM và œ xœ =n, tM(x)= t} ị ớ c đoán nh n b i m t máy Turing ượ t đ nh):
ấ ị
ộ ậ ở t ậ ượ ở ấ ọ ≥ 0. ớ Đ nh nghĩa l p NP (thông qua máy Turing không t
+ NP là l p các bài toán đ
ớ
t đ nh.trong th i gian đa th c
không t
ứ
ờ
ấ ị
+ M t ngôn ng L là đoán nh n đ
c b i máy Turing không t
ộ
ữ
đ nh và đa th c P(n) sao cho:
ứ
ị
L= LM và TM(n) ≤ P(n) v i m i n
M t bài toán g i là NP n u ngôn ng t ng ng c a nó ữ ươ ứ ủ ế ọ ộ
thu c l p NP.
ộ ớ + P ˝ NP hi n nhiên vì m i máy Turing t t đ nh đ u là ể ỗ ấ ị ề máy Turing b t đ nh không bao gi ấ ị ch n l a b
ờ ọ ự ướ c ch n
ọ l u chuy n
ể
ư ên q(n) v i K = |
ớ G Nh v y s d đoán t
ư ậ ố ự ố i đa s là K
ẽ |. Do đ ộ dài c a xâu d đoán không quá q(n) nên quá trình ki m ủ ự ể q(n) .Nh ư tra m i d đoán có đ ph c t p cũng là q(n). K ỗ ự ứ ạ ộ v y đ ph c t p c a quá trình ki m tra trên m t DTM
ậ ứ ạ ủ ể ộ ộ p(n)) cho bài toán II là s là O(2 ẽ2. NGÔN NG VÀ L
C Đ MÃ HÓA
Ữ
ƯỢ Ồ
3. MÁY TURING T T Đ NH VÀ L P P
Ấ
Ớ
Ị
3. MÁY TURING T T Đ NH VÀ L P P
Ấ
Ớ
Ị
- 3
- 2
- 1
0
1
2
3
4
3. MÁY TURING T T Đ NH VÀ L P P
Ấ
Ớ
Ị
2. MÁY TURING T T Đ NH VÀ L P P
Ấ
Ớ
Ị
3. MÁY TURING T T Đ NH VÀ L P P
Ấ
Ớ
Ị
3. MÁY TURING T T Đ NH VÀ L P P
Ấ
Ớ
Ị
3. MÁY TURING T T Đ NH VÀ L P P
Ấ
Ớ
Ị
3. MÁY TURING T T Đ NH VÀ L P P
Ấ
Ớ
Ị
3. MÁY TURING T T Đ NH VÀ L P P
Ấ
Ớ
Ị
Quá trình th c hi n:
ự
ệ
4. L P PỚ
4. L P PỚ
2.3.Máy Turing không t
t đ nh& L p NP
ấ ị
ớ
2.3.Máy Turing không t
t đ nh& L p NP
ấ ị
ớ
ng t
ươ
ấ ị
c ượ
t đ nh:
0* đ
ạ
ự
ầ
ướ
ắ
ở ơ
ầ
ầ
ỉ ế
ừ
ầ
ạ
Ho t đ ng t
nh máy Turing t
ự ư
ạ ộ
Gi
s máy làm vi c v i m t Input x
ộ
ớ
ệ
ả ử
ế œ xœ c a băng.
đ t vào các ô t
1 đ n
ủ
ừ
ặ
Giai đo n ph ng đoán đ
c th c hi n trên ph n
ệ
ượ
ỏ
c đánh s
băng bên trái c a d li u vào (các ô đ
ố
ượ
ủ ữ ệ
c khi quá trình tính toán b t đ u,
-1,-2,...) tr
c th c hi n b i c ch ph ng đoán và đ u
đ
ỏ
ế
ệ
ự
ượ
t lên các ô đánh –1, -2..m i ô
ph ng đoán ch vi
ỏ
ỗ
ộ S * cho đ n khi d ng l
i
m t kí hi u nào đó thu c
ế
ệ
ộ
ạ
ộ ừ ˛
0* trên phía trái c a ph n băng
u
ta có m t t
ủ
ch a Input (g i là t
c d đoán) và giai đo n
đ
ừ ượ ự
ọ
ph ng đoán hoàn thành
ứ
ỏ
2.3.Máy Turing không t
t đ nh& L p NP
ấ ị
ớ
+Y u t
không t
t đ nh là
ch trong giai đo n
ế ố
ấ ị
ở
ạ
ỗ
ph ng đoán vi c vi
t kí t
nào vào các ô –1,-2,-3...
ệ
ỏ
ế
ự
không xác đ nh t c là có th vi
ể ế
ứ
ị
t theo nhi u kh
ả
ề
năng khác nhau
+Có th hình dung n u coi m i quá trình tính toán
ế
ể
ỗ
có môt input x trên máy Turing t
t đ nh M ch là
ấ ị
ỉ
ng tính toán” (a computation path) thì m i
m t “đ
ộ
ườ
ỗ
quá trình tính toán v i m i input x trên NDTM là
ỗ
ớ
m t “cây tính toán” (a computation tree) v i nhi u
ề
ộ
ớ
đ
ng tính toán đ
c x lý đ ng th i
ườ
ượ ử
ờ
ồ
2.3.Máy Turing không t
t đ nh & L p NP
ấ ị
ớ
NDTM
DTM
qY/qN
qN
qY
S khác bi
ự
t
ệ
2.3.Máy Turing không t
t đ nh& L p NP
ấ ị
ớ
2.3.Máy Turing không t
t đ nh& L p NP
ấ ị
ớ
2.3.Máy Turing không t
t đ nh& L p NP
ấ ị
ớ
2.4. Quan h gi a l p P và NP
ệ ữ ớ
2.4. Quan h gi a l p P và NP
ệ ữ ớ
(Gap-Borodin,1972): Đ i v i m i bài toán
ố ớ
ỗ
NP t n t
i đa th c p(n) sao cho II đoán nh n
ồ ạ
ứ
ậ
c v i máy Turing t
ớ
ấ ị
t đ nh có đ ph c t p là
ộ
ứ ạ
Đ nh lý
ị
II ˛
đ
ượ
O(2p(n))
Ch ng minh:
ứ
Gi
s A là thu t toán th i gian không t
t đ nh cho
ả ử
ậ
ờ
ấ ị
II, q(n) là đa th c bi u di n đ ph c t p A tr
ứ ạ
ứ
ể
ễ
ộ
NTM. V i m i Input có đ dài n t n t
ồ ạ
ỗ
ớ
ộ
i xâu có đ
ộ
dài l n nh t là q(n) thu c ngôn ng t
ng ng c a
ữ ươ
ấ
ộ
ớ
ứ
ủ
bài toán II đ quá trình đoán nh n cho câu tr l
i là
ả ờ
ể
ậ
“yes” không m t quá q(n) b
c.
ấ
ướ
2.4. Quan h gi a l p P và NP
ệ ữ ớ
