Giáo trình Lý thuyết tính toán

(n) 
Tất cả các họ trên được gọi là các lớp của độ phức tạp. Từ các định nghĩa trên, ta 
suy ra rằng : 
DSPACE (f (n)) ⊆ NSPACE (f (n)) 
DTIME (f (n)) ⊆ NTIME (f (n)) 
và, nếu f ≤ g, thì: 
DSPACE (f (n)) ⊆ DSPACE (g (n)) 
NSPACE (f (n)) ⊆ NSPACE (g(n)) 
DTIME (f (n)) ⊆ DTIME (g (n)) 
NTIME (f (n)) ⊆ NTIME (g(n)) 
Giả sử L là ngôn ngữ được cho trong ví dụ 6. 1 trước đây, ta có: 
L ∈ DTIME (n) ∩ DSPACE (log2 (n)), 
nhưng ta cũng có : 
 L ∈ DTIME (n2) ∩ NTIME ( n) ∩ DSPACE (n) 
96 Lý thuyết tính toán 
II.1. Hiện tượng nén 
Giả sử T là một máy Turing có độ phức tạp về bộ nhớ là S(n) = f(n), bằng cách sử 
dụng một bảng chữ trong đó, mỗi ký tự biểu diễn k ký tự liên tiếp của bảng chữ của T, 
ta có thể xây dựng một máy Turing T’ nhận biết cùng ngôn ngữ và có cùng độ phức 
tạp về bộ nhớ là f(n)/k. Máy T’ này mã hóa trên bảng chữ mới thông tin ghi trên mỗi 
một băng làm việc (nhớ rằng không kể không gian nhớ dùng để ghi dữ liệu vào). 
Rõ ràng, nhờ phương pháp này, bằng cách sử dụng một thừa số c không đổi, ta có 
thể giảm bớt độ phức tạp về bộ nhớ để nhận biết một ngôn ngữ đã cho. 
Nếu T là một máy Turing off-line có k băng, ta có thể nhận biết cùng một ngôn 
ngữ bằng cách sử dụng một máy Turing off−line chỉ có một băng, sử dụng cùng một 
phương pháp để không sử dụng không gian nhớ nhiều hơn T. Đối với độ phức tạp về 
bộ nhớ, việc ta giảm bớt số lượng băng làm việc không có nghĩa, cho nên, từ nay, ta 
chỉ xét đến các máy Turing off−line có một băng, thậm chí, trong trường hợp S(n) = 
n, ta chỉ xét các máy Turing có một băng mà không thêm gì nữa. 
Ta cũng có thể áp dụng phương pháp nén vừa trình bày trên đây đối với độ phức 
tạp về thời gian. Tuy nhiên phương pháp này không miễn đọc dữ liệu, mà cần một 
thời gian n + 1 để đọc dữ liệu có độ dài n. Như vậy, ta có thể giảm bớt nhờ một thừa 
số không đổi là c ngay khi T(n)/n có khuynh hướng tăng vô hạn. 
Bây giờ ta xem xét hiệu quả của độ phức tạp về thời gian khi giảm bớt số lượng 
các băng làm việc. 
Khi giảm bớt còn một băng, phân tích phương pháp đã trình bày ở chương 3 để 
chuyển từ k băng về một băng, ta chứng minh được : 
 L ∈ DTIME (T (n)) ⇒ L được thừa nhận bởi một máy Turing một băng 
với chi phí thời gian là T2(n). 
Khi cần thực hiện việc sao chéo, ta có thể chuyển từ một băng sang hai băng 
nhằm làm giảm đáng kể số bước tính toán. Ta chứng minh được rằng việc rút gọn còn 
hai băng thay vì chỉ còn một băng làm tối ưu rõ rệt chi phí về thời gian : 
 L ∈ DTIME (T (n)) ⇒ L được thừa nhận bởi một máy Turing có hai băng 
với thời gian T (n).log2(T (n)) 
Tuy nhiên, để trả lời câu hỏi : 
Với chi phí thời gian nhiều hơn (tương ứng : nhiều bộ nhớ hơn) thì người ta có 
nhận biết được thực sự nhiều ngôn ngữ hơn không ? 
ta có mệnh đề sau đây : 
Mệnh đề 6.1 : 
Với mọi hàm đệ quy toàn phần f, tồn tại một ngôn ngữ đệ quy L không thuộc họ 
DTIME (f (n)) (một cách tương ứng : không thuộc họ DSPACE (f (n))). 
Chứng minh : 
Sử dụng kỹ thuật đường chéo cho ngôn ngữ : 
L = { wi | Ti không thừa nhận câu wi sau f (|wi|) bước tính toán } 
Thật vậy, L là một ngôn ngữ đệ quy không thuộc họ DTIME (f (n)). 
Độ phức tạp tính toán 97 
Giữa các phép đo độ phức tạp tính toán khác nhau này, ta có thể thiết lập các mối 
quan hệ. Một số quan hệ dễ dàng nhận được như sau : 
L ∈ DTIME (f (n)) ⇒ L ∈ DSPACE (f (n)) 
Thật vậy, máy Turing thăm một ô tại mỗi bước tính toán. Trường hợp xấu nhất 
xảy ra khi tất cả các ô đều khác nhau. 
L ∈ DSPACE (f (n)) và f (n) = log2 (n) ⇒ L ∈ DTIME (cf (n)) 
Thật vậy, nếu f (n) = log2 (n), tồn tại một hằng c sao cho cf(n) là lớn hơn số các 
cấu hình phân biệt có độ dài tối đa là f (n) của một máy Turing đã cho. 
L ∈ NTIME (f (n)) ⇒ L ∈ DTIME (cf (n)). 
Thật vậy, quan hệ này đến từ việc tăng thêm số cấu hình phân biệt đối với một dữ 
liệu có độ dài n. Thời gian tăng thêm là cf (n). 
Sau đây là một quan hệ được cho bởi định lý Savitch. 
Định lý Savitch WJ : 
L ∈ NSPACE (f (n)) và f (n) = log2 (n) ⇒ L ∈ DSPACE (f2 (n)). 
II.2. Các họ P, NP và P−bộ nhớ (P−space) 
Các lớp của độ phức tạp tính toán sau đây đủ quan trọng để có tên riêng : 
P = U
1i ≥
DTIME (ni), 
NP = U
1i ≥
NTIME (ni). 
Như vậy : 
P là lớp các ngôn ngữ được nhận biết bởi một máy Turing đơn định 
cần một lượng thời gian bậc đa thức, 
NP là lớp các ngôn ngữ được nhận biết bởi một máy Turing 
không đơn định cần một lượng thời gian bậc đa thức. 
Ta đưa vào các lớp P−bộ nhớ (P−space) và NP−bộ nhớ (NP−space) như sau : 
P−bộ nhớ = U
1i ≥
 DSPACE (ni), 
NP−bộ nhớ = U
1i ≥
 NSPACE (ni). 
P−bộ nhớ là lớp các ngôn ngữ được nhận biết bởi một máy Turing 
đơn định cần một lượng bộ nhớ bậc đa thức, 
NP−bộ nhớ là lớp các ngôn ngữ được nhận biết bởi một máy Turing 
không đơn định cần một lượng bộ nhớ bậc đa thức. 
Rõ ràng ta có đẳng thức : 
98 Lý thuyết tính toán 
P−bộ nhớ = NP−bộ nhớ 
Và ta có các bao hàm sau đây : 
DSPACE (log2 (n)) ⊆ P ⊆ NP ⊆ P−bộ nhớ = NP−bộ nhớ. 
Trong thực tế, người ta ước lượng một bài toán là : 
− xử lý được (tractable), nếu bài toán đó thuộc lớp P 
hay giải được (workable) 
− không xử lý được (untractable), nếu bài toán đó không thuộc lớp P. 
hay không giải được (unworkable) 
Vì vậy, ít khi người ta giải quyết những bài toán cần một lượng thời gian và bộ 
nhớ dạng đa thức có bậc lớn hơn 4 vì sẽ làm tăng độ phức tạp tính toán. 
III. Rút gọn đa thức và các bài toán NP−đầy đủ 
III.1. Khái niệm 
Rút gọn đa thức (polynomial reduction) là làm mịn (refinement) khái niệm rút gọn 
số học đã định nghĩa ở chương 5. Ta vẽ lại sơ đồ rút gọn số học như sau : 
Hình 6.1 Rút gọn bài toán A về bài toán B 
Định nghĩa 6.1 
Người ta nói bài toán A được rút gọn kiểu đa thức về bài toán B nếu tồn tại một 
máy Turing dừng cho mọi dữ liệu và thực hiện tính hàm f hết một lượng thời gian đa 
thức (polynomial time). Hàm f được xác định từ tập hợp các biểu diễn dữ liệu của 
bài toán A vào tập hợp các biểu diễn dữ liệu của bài toán B, thỏa mãn : 
w ∈ LA ⇔ f (w) ∈ LB 
Người ta nói rằng máy Turing này đã thực hiện kiểu đa thức (polynomially work) 
việc rút gọn bài toán A về bài toán B. Từ đó, ta có mệnh đề sau : 
Mệnh đề 6.2 : 
Nếu bài toán A được rút gọn kiểu đa thức về bài toán B, thì nếu B là một bài toán 
thuộc lớp P (một cách tương ứng : thuộc lớp NP), thì A cũng là một bài toán thuộc 
lớp P (một cách tương ứng : thuộc NP). 
Người ta cũng nói rằng các lớp P và NP là đóng đối với phép rút gọn đa thức. 
LPA 
S*\LPA
LPB 
S*\LPB
Anh của f từ các 
biểu diễn dữ liệu của 
bài toán A 
Biểu diễn dữ liệu 
của bài toán B 
Biểu diễn dữ 
liệu của bài 
toán A 
f 
f 
Độ phức tạp tính toán 99 
Chứng minh : 
Thật vậy, giả sử T là một máy Turing luôn luôn dừng và nhận biết ngôn ngữ LB 
một lượng thời gian đa thức. Giả sử T’ là một máy Turing thực hiện việc rút gọn hết 
một lượng thời gian đa thức từ bài toán A về bài toán B. Rõ ràng, máy Turing T’ next 
T luôn luôn dừng và nhận biết ngôn ngữ LA một lượng thời gian đa thức. 
Một cách tương tự, ta định nghĩa khái niệm rút gọn sử dụng bộ nhớ logarit. 
Định nghĩa 6.2 : 
Người ta nói bài toán A được rút gọn về bài toán B cần một lượng bộ nhớ logarit 
nếu tồn tại một máy Turing luôn luôn dừng cho mọi dữ liệu và thực hiện tính hàm f 
sử dụng một lượng bộ nhớ theo logarit. Hàm f được xác định từ tập hợp các biểu 
diễn dữ liệu của bài toán A vào tập hợp các biểu diễn dữ liệu của bài toán B, thỏa 
mãn : 
w ∈ LA ⇔ f (w) ∈ LB 
Ta có mệnh đề sau : 
Mệnh đề 6.3 : 
Lớp P đóng đối với phép rút gọn sử dụng bộ nhớ logarit. 
Việc chuyển một chương trình RAM thành một chương trình của một máy Turing 
được thực hiện sao cho thời gian chạy của máy Turing được tính theo số bước tính 
toán, là một đa thức theo thời gian chạy chương trình của máy RAM được tính theo 
số các lệnh (instructions) đã thực hiện. 
Tương tự, việc chuyển một công thức trong một ngôn ngữ bậc cao thành một công 
thức của một máy RAM được thực hiện sao cho thời gian chạy công thức của máy 
RAM được tính theo số các lệnh của RAM đã thực hiện, là một đa thức về thời gian 
chạy công thức trên ngôn ngữ bậc cao, được tính theo số các lệnh đã thực hiện. 
Từ đó, việc định nghĩa các lớp P và NP được dựa trên mô hình các máy Turing 
nhưng không phụ thuộc chính xác vào mô hình này, và để đảm bảo rằng một ngôn 
ngữ là thuộc một trong hai lớp này, chỉ cần đếm số lượng các phép toán một cách đơn 
giản. 
III.2. Các bài toán cổ điển 
Sau đây là sáu bài toán cổ điển trong Tin học. 
1. Bài toán tô màu các đỉnh của một đồ thị 
Dữ liệu : Một đồ thị G = và một số nguyên k. 
Câu hỏi : Ta có thể tô mỗi đỉnh của đồ thị một màu sao cho cứ hai đỉnh của đồ thị 
được nối với nhau bởi một cung thì không được tô cùng màu được chọn 
trong số k màu ? 
2. Bài toán lập kế hoạch làm việc 
Dữ liệu : Cho n việc và một số nguyên k, mỗi việc được đặc trưng bởi bộ ba các 
số nguyên (ti, di, pi), với ti, di, và pi lần lượt biểu diễn thời gian thực 
hiện, thời gian kết thúc và hình phạt ứng với việc thứ i. 
100 Lý thuyết tính toán 
Câu hỏi : Có thể sắp xếp các việc sao cho tổng số các hình phạt là nhỏ hơn hoặc 
bằng k ? Nói cách khác, với mọi hoán vị P của n số nguyên đầu tiên, ta 
kết hợp một số nguyên : 
Pp = 
p(j)
j 1, n
p (j) p(r)
r 1, j
 P t d 
 0
= =
⎧ ⎡ ⎤= >⎣ ⎦⎪⎨⎪=⎩
∑ ∑nãuú
nãúu khäng
và người ta tìm một hoán vị P nếu hoán vị P tồn tại sao cho Pp = k. 
3. Bài toán sắp xếp trong các thùng chứa 
Dữ liệu : Cho số nguyên c (dung lượng của các thùng), n vật đặc trưng bởi các 
kích thước s1, s2, ..., sn với 0 < si ≤ c và một số nguyên k. 
Câu hỏi : Có thể đặt n vật vào nhiều nhất là k thùng chứa được không ? 
4. Bài toán ba-lô (rucksack) 
Dữ liệu : Cho một số nguyên c (kích thước ba-lô) và n vật có các kích thước lần 
lượt s1, s2, ..., sn. 
Câu hỏi : Có thể bỏ đầy hoàn toàn ba-lô bởi một số vật lấy từ n vật đã cho ? 
5. Bài toán thỏa mãn các biểu thức boolean ở dạng chuẩn hội 
Dữ liệu: Một biểu thức boolean ở dạng chuẩn hội. 
Câu hỏi : Có thể gán giá trị nào đó cho các biến làm biểu thức thỏa mãn ? 
6. Bài toán đường đi Hamilton 
Dữ liệu: Một đồ thị G = . 
Câu hỏi : Tồn tại hay không một đường đi Hamilton (đi qua tất cả các đỉnh) trong 
đồ thị đã cho ? 
III.3. Ví dụ về rút gọn kiểu đa thức 
Bây giờ ta xét một ví dụ : hãy rút gọn kiểu đa thức bài toán ba-lô về bài toán sắp 
đặt các việc có hình phạt. 
Giả sử I = (s1, s2, ..., sn; c) là một dữ liệu vào cho bài toán ba-lô. 
- Nếu c 
n 1, j
s j∑
=
< thì câu trả lời là không. 
Khi đó, ta xét bài toán sắp đặt các việc có hình phạt được định nghĩa bởi 
ti = 2, di = pi = 1 và k = 0 với câu trả lời không. 
- Nếu trái lại, c 
n 1, j
s j∑
=
≥ thì câu trả lời là thoả mãn. 
Ta xét bài toán sắp đặt các việc có hình phạt được định nghĩa bởi ti = pi = si và 
di = c với ∀i = 1 .. n, và k = c 
n 1, j
s j∑
=
− 
Bây giờ ta kiếm tra trường hợp cá biệt I của bài toán ba-lô có một lời giải nếu và 
chỉ nếu bài toán sắp đặt các việc có hình phạt mà ta sẽ đưa về cũng có một lời giải : 
Độ phức tạp tính toán 101 
Nếu bài toán ba-lô có một lời giải, khi đó tồn tại một tập hợp con J thuộc khoảng 
{ 1, ..., n } sao cho ∑j∈J sj = c. Ta chọn một hoán vị P sao cho tất cả các việc có chỉ 
số trong J được chọn trước các việc khác. 
Cả || J || việc này đều được làm xong trước ngày kết thúc của chúng, trong khi đó, 
các việc khác được làm xong sau ngày kết thúc, từ đó sinh ra một hình phạt: 
∑J = || J|| + 1, npP (J) = ∑J = || J|| + 1, n sP (J) 
= ∑J = 1, n J ∈J 
= ∑J = 1, n sJ - c = k 
Như vậy, các việc được làm xong với một hình phạt nhỏ hơn hoặcbằng k, giả sử m 
là số nguyên lớn nhất sao cho m việc đầu tiên được làm xong trước ngày kết thúc 
chung của chúng là c. Như vậy, ta có: ∑J -- 1, m tP(J) ≤ c và hình phạt là : ∑J = m + 1, n 
PP(J) ≤ k 
Do ti = Pi = si, ta có 
∑J - 1, m tP(J)z + ∑J - m + 1, n PP(J) = ∑J - 1,n sJ = c + k 
Do đó, cả hai bất đẳng thức đều bằng nhau và các vật có chỉ số P(j) với 
j = 1..m sẽ làm đầy ba-lô. Ta cần kiểm chứng rằng việc rút gọn là theo thời gian đa 
thức, nghĩa là chỉ có một phép tính duy nhất là tính giá trị ∑J - 1, n sJ - c. 
Rõ ràng phép tính này đòi hỏi một thời gian đa thức. Việc xây dựng bài toán sắp 
đặt các việc có hình phạt sẽ là có thời gian hằng nếu số nguyên này âm, có thời gian 
tuyến tính nếu số nguyên này dương. 
Cho đến lúc này, ta chưa biết có bài toán nào trong sáu bài toán trên thuộc vào lớp 
không P. Tuy nhiên, người ta dễ dàng chứng minh được rằng chúng đều thuộc lớp 
NP. 
Ví dụ 6. 2 
Bài toán tô màu các đỉnh của một đồ thị là thuộc lớp NP. 
Thật vậy, máy Turing không đơn định sau đây nhận biết ngôn ngữ kết hợp với bài 
toán này về thời gian tuyến tính (và do vậy, là đa thức) : trong thời gian đầu, máy 
Turing thực hiện tô cho mỗi đỉnh, một cách không đơn định, một màu nào đó trong số 
k màu. 
Sau đó, máy Turing kiểm tra việc tô màu này đã thỏa mãn chưa, nghĩa là kiểm tra 
tại các mút của các cung xem các đỉnh có cùng một tô một màu không ?. 
Bây giờ ta chứng minh rằng thực tế tất cả sáu bài toán trên đều có thể rút gọn kiểu 
đa thức từ bài toán kia. Từ đó, cả sáu bài toán đều thuộc lớp P nếu và chỉ nếu một 
trong chúng thuộc P. Ta có định nghĩa sau đây : 
Định nghĩa 6.3 
Một bài toán là NP-cứng (NP - Comlete) nếu nó ở trong lớp NP. 
Rõ ràng, định nghĩa trên có ích vì tồn tại những bài toán NP-đầy đủ như vậy. 
102 Lý thuyết tính toán 
Định ký Cook - 1971 (Stephen Cook) : 
Bài toán về tính thỏa mãn của các biểu thức boolean dưới dạng chuẩn hội là một 
bài toán NP -đầy đủ. 
Ta không chứng minh định lý này. 
Bổ đề 6. 1 
Cả sáu bài toán trên đây đều là NP-đầy đủ. 
Ta có mệnh đề sau: 
Mệnh đề 6. 4 
P = NP nếu và chỉ nếu tồn tại ngôn ngữ L ∈ P sao cho L là NP-đầy đủ. 
Bài tập 
1. Xét ngôn ngữ L = { wcw’ | w ∈ { a, b }* và w ≠ w’ } 
Chứng minh rằng L ∈ NTIME (n) ∩ DSPACE (log2 (n)). 
2. Chứng minh rằng cả sáu bài toán đã nêu đều có thể rút gọn kiểu đa thức từ bài 
toán này về bài toán kia. 
3. Một đồ thị được gọi là đầy đủ nếu có hai đỉnh bất kỳ được nối với nhau bới một 
cạnh. Đồ thị được gọi là k-đầy đủ nếu tồn tại một đồ thị con có k đỉnh là đầy đủ. 
Bài toán đầy đủ k-đầy đủ như sau: 
Dữ liệu : Một đồ thị G và một số nguyên k 
Câu hỏi : G có phải là k-đầy đủ? 
Chứng minh rằng bài toán đồ thị k-đầy đủ là bài toán NP đầy đủ. 
4. Những bài toán sau đây thuộc lớp NP, thuộc lớp P, thuộc lớp NP-bộ nhớ ? 
Bài toán nào là NP-đầy đủ ? 
a) Dữ liệu : Một câu w biểu diễn một biểu thức Boolean. 
Câu hỏi : Câu w có phải là một hằng đúng (tautology) không ? 
b) Dữ liệu : Một máy Turing T trên bảng chữ { a, b }. 
Câu hỏi : Có tồn tại không một câu w ∈ S* có độ dài n sao cho máy Turing 
 T nhận biết w hết một lượng thời gian nhỏ hơn boặc bằng n ? 
c) Dữ liệu : Một máy Turing trên bảng chữ { a, b }. 
Câu hỏi : Tồn tại hay không một câu có độ dài n sao cho T nhận biết 
 câu này về bộ nhớ nhỏ hơn hoặc bằng n ? 
d) Dữ liệu : Một cặp đồ thị (G, G’). 
Câu hỏi : Đồ thị G’ có đẳng cấu (isomorphic) với một đồ thị con của G hay 
 không ?