LỜI NÓI ĐẦU
Mỗi ngành khoa học đều có cơ sở lý thuyết của nó. Khoa học máy tính
(Tin học) cũng vậy: cơ sở lý thuyết của khoa học máy tính là lý thuyết
oâtoâmat.
Lý thuyết oâtoâmat nghiên cứu về các mô hình toán học cho các thiết bị
tính toán (các máy tính toán), trên cơ sở đó cho phép chúng ta xác định những
khả năng tính toán của chúng, nghĩa là xác định những gì chúng có thể tính
được và những gì chúng không thể tính được. Nói cách khác, trên cơ sở các mô
hình toán học cho các thiết bị tính toán, chúng ta có thể biết được những bài
toán nào giải được bằng máy tính và những bài toán nào không giải được. Đi
xa hơn, chúng ta có thể xác định ranh giới giữa những bài toán có thể tính
được một cách thực tế (có thể xây dựng được các chương trình máy tính để
giải) với những bài toán về nguyên tắc có thể tính được nhưng không thực tế
(các bài toán nan giải, intractable problem) vì mất quá nhiều thời gian, ngoại
trừ một số tình huống cụ thể có kích thước nhỏ. Lĩnh vực nghiên cứu lý thú
này được gọi là Lý thuyết độ phức tạp tính toán (computational complexity
theory).
Một cách trực quan, Thuật toán là một dãy hữu hạn các bước cho ta cách
giải bài toán. Ta có thể hình dung cụ thể hơn: Thuật toán là một chương trình
máy tính được viết bằng một ngôn ngữ lập trình nào đấy. Một cách toán học,
Thuật toán là một máy Turing đơn định, viết tắt là DTM (Deterministic Turing
Machine). Tập L gồm các Input được M chấp nhận (Yes) gọi là ngôn ngữ
chấp nhận bởi máy M, kí hiệu L(M).
Khi giải một bài toán cụ thể, không những ta chỉ cố gắng tìm một thuật
toán giải được bài toán đã cho, mà còn muốn tìm một thuật toán “tốt nhất”.
Trong nhiều trường hợp tốt nhất được hiểu là “nhanh nhất” , và ta đi đến khái
niệm về độ phức tạp thời gian.
Độ phức tạp của thuật toán chính là yếu tố cơ sở để phân loại các bài
toán. Các bài toán mà thuật toán giải nó có độ phức tạp thời gian cấp từ đa
thức trở xuống được gọi là thuộc lớp P. Các bài toán mà thuật toán giải nó là
thuật toán không đơn định và có độ phức tạp thời gian là đa thức được gọi là

có nghóa là sau khi đọc kí tự a ở trạng thái q, máy chuyển sang trạng
thái q’, viết a’ ở vò trí của a (có thể a’= a, nghóa là không thay đổi)
và dòch chuyển đầu đọc-viết tùy theo m.
Nếu đầu đọc-viết sắp “rơi khỏi“ băng tức là một dịch chuyển trái
(tương ứng phải) được chỉ thò khi máy đang đọc ô trái nhất (tương
ứng phải nhất) của băng thì một ô trống mới được tự động thêm
vào ở đầu mút tương ứng. Khả năng mở rộng vô hạn bộ nhớ
ngoài có thể được xem như một đặc trưng phần cứng có sẵn của
mỗi máy Turing.
Dạng vào-ra của một máy Turing được đặc tả như sau : máy bắt đầu tính
tốn bằng cách đọc kí tự trái nhất của một từ vào cho trước ở một trạng thái bắt
đầu đặc biệt. Thơng tin vào được chấp nhận nếu tính tốn đạt đến một trạng
thái kết thúc đặc biệt. Nếu máy được xem như một máy dịch chứ khơng phải
một máy chấp nhận thì từ trên băng, sau khi máy đã đạt đến trạng thái kết
3
thúc, lập thành đường ra đối với từ vào đã cho. Khi đó một số kí tự nào đó trên
băng có thể bỏ qua.
Như vậy, băng có thể được xem vừa như kênh vào-ra vừa như bộ nhớ
vơ hạn tiềm năng. Những khác nhau cơ bản giữa các máy Turing và các loại
ôtômát khác đó là, một ôtômát hữu hạn chỉ có bộ nhớ trong được xác
định bởi tập trạng thái hữu hạn của nó, băng vào khơng được dùng như bộ
nhớù bổ sung, một ôtômát hữu hạn chỉ đọc thơng tin vào bằng cách qt
từ trái sang phải. Trong một ôtômát tuyến tính giới nội, bộ nhớ ngồi bị
giới hạn trên bởi kích thước của từ vào. Do đó, rõ ràng máy Turing tổng qt
hơn các mơ hình tính tốn khác, mỗi thuật tốn có thể được thực hiện bởi một
máy Turing.
Thực chất, máy Turing là một mơ hình máy. Nó phân tồn bộ q trình
hoạt độâng ra thành các bước thao tác rất đơn giản. Bản thân máy Turing là
một mơ hình khái qt và đơn giản có thể mơ hình hố một q trình tính tốn
bất kỳ. Trong phần này ta chỉ xét đến máy Turing đa băng. Máy Turing là một

Ban đầu máy ở trạng thái :
4
X
1
X
2
X
k
q
Đầu chỉ huy
Băng 1
Băng 2
…………
Băng k
Sau một bước tính toán máy ở trạng thái:
2/ Máy Turing đơn định đa băng:
2.1. Định nghĩa 1:
∑ = {X
1
, X
2
, …., X
n
} được gọi là một bảng chữ nếu nó hữu hạn và
không rỗng. Mỗi phần tử của nó được gọi là kí tự. Một xâu trên bảng
chữ ∑ là một dãy hữu hạn các ký tự được xếp liền nhau.
Ví dụ : α = X
i1
……X
it

5
Y
1
Y
2
Y
k
q
Đầu chỉ huy
Băng 1
Băng 2
…………
Băng k
Máy Turing đơn định đa băng là một bộ bảy M = (Q, ∑, ∆, δ, B, q
o
, q
f
)
trong đó:
• Q là tập trạng thái hữu hạn khác rỗng, q
o
, q
f
Q
• ∑ là bảng chữ ngoài
• ∆ là tập con của ∑ và gọi là bảng chữ trong
• δ là hàm chuyển, δ:
•
• với d
i

để hướng hoạt động sau đó saïng
trái (L), sang phải (R), hay dừng (S).
- Ở băng 2 được thay B bởi và d
2
là hướng hoạt động.
………
- Ở băng k được thay B bởi và d
k
là hướng hoạt động.
Ta có thể minh họa bằng hình vẽ sau:
Ban đầu của máy ở trạng thái :
6
a
3
ε
q
Đầu chỉ huy
Băng 1
Băng 2
…………
Băng k
a
1
a
2
… a
k
ε
ε
ε

i
và x
i
y
i
là một xâu nằm trên băng thứ i. Hình
trạng đầu là (q
o
α, q
o
, q
o
, …, q
o
).
• Ký hiệu dãy xâu ( ,…, ) là D
1
thì một bước thực hiện của máy
Turing là quá trình chuyển từ hình trạng D
1
sang D
2
và ký hiệu
D
1
D
2

• Nếu có chỉ số t mà có D
1

2
… a
k
ε
ε
ε
…
a’
k
ε
ε
…
f. Định nghĩa 5:
Xâu được nhận biết bởi máy Turing M
Giả sử M = , là một xâu trong bảng chữ
( bảng chữ trong).
Khi đó ta nói M nhận biết nếu (q
o
a
1
… a
n
, q
o
, …, q
o
) ( ) với
điều kiện thì

.

Q = {q
o
, q
1
, q
2
, q
3
, q
4
, q
5
}, ∑ = {ε, X, 0, 1}, q
f
= q
5
, ∆ = {0, 1}
Hàm δ thực hiện theo bảng sau:
Trạng thái
cũ
Ký tự cũ Ký tự mới Trạng thái
mới
Băng 1 Băng 2 Băng 1 Băng 2
q
o
0
ε
0, S X, R q
1
1

2
ε
X
ε, L
X, R q
3
q
3
0 0 0, S 0, R q
4
1 1 1, S 1, R q
4
q
4
0 0 0, L 0, S q
3
0 1 0, L 1, S q
3
1 0 1, L 0, S q
3
1 1 1, L 1, S q
3
0
ε
0, S
ε, S
q
5
1
ε

8
+ (0111q
1
0, X0111q
1
)
+ (01110q
1
, X01110q
1
)
+ (01110q
2
, X0111q
2
0)
+ (01110q
2
, X011q
2
10)
+ (01110q
2
, X01q
2
110)
+ (01110q
2
, X0q
2

110)
+ (01q
3
110, X01q
3
110)
+ (01q
4
110, X011q
4
10)
+ (0q
3
1110, X011q
3
10)
+ (0q
4
1110, X0111q
4
0)
+ (q
3
01110, X0111q
3
0)
+ (q
4
01110, X01110q
4

• là bảng chữ ngoài
• là tập con của và gọi là bảng chữ trong
• , là kí tự trắng
• q
o
là trạng thái đầu, q
F
là trạng thái kết thúc
• , với là tập các tập con
của
3.2. Định nghĩa 9 : Quá trình tính toán của máy Turing không đơn
định M.
Chọn một giá trị của giả sử là (r, (y
1
,d
1
), (y
2
,d
2
),……, (y
k
,d
k
))
với d
i
= . Như vậy máy chuyển sang trạng thái mới r và x
i
được thay

được gọi là một quá trình tính toán của máy Turing M ( hay còn gọi
là dẫn xuất).
3.3. Định nghĩa 10 :
10
Giả sử M là máy Turing không đơn định đa băng. T(n) là độ phức tạp
tính toán thời gian của M nếu với mỗi xâu w có độ dài n thì đều tồn tại một
dẫn xuất D
1
D
t
để nhận biết w mà có nhiều nhất là T(n) bước.
3.4. Định nghĩa 11:
Giả sử M là máy Turing không đơn định đa băng. S(n) là độ phức tạp
dung lượng nhớ của M nếu với mọi xâu w có độ dài n thì đều tồn tại một
dẫn xuất để nhận biết w mà sử dụng nhiều nhất là S(n) oâ khác nhau trên
mỗi băng.
4. Sự tương ñương của máy Turing một băng và máy Turing đa băng:
Cần nhớ lại rằng các ngôn ngữ kể được đệ quy được định nghĩa là
những ngôn ngữ được kiểm nhận bởi máy Turing một băng. Chắc chắn
rằng máy Turing đa băng đều kiểm nhãn tất cả các ngôn ngữ kể được đệ
quy vì máy một băng chính là máy đa băng. Tuy nhiên liệu có những ngôn
ngữ không phải kể được đệ quy nhưng được máy đa băng kiểm nhận hay
không? Câu trả lời là không, và chúng ta sẽ chứng minh điều này bằng
cách chỉ ra cách mô phỏng một máy Turing đa băng bằng một máy một
băng.
Định lý: Mỗi ngôn ngữ được kiểm nhận bằng một máy Turing đa băng
đều là kể được đệ quy.
Chứng minh: chứng minh này được gợi tả trong hình sau:
X
A

của M. N cũng biết được trạng thái của M vì nó được lưu trong bộ phận
điều khiển của N, vì thế N biết được M sẽ thực hiện bước chuyển nào.
N bây giờ sẽ thăm lại mỗi dấu ghi trên băng của nó, thay đổi ký hiệu
trong rãnh biểu diễn cho băng tương ứng của M và di chuyển dấu ghi sang
phải hoặc sang trái nếu cần. Cuối cùng N thay đổi trạng thái của M như
được ghi trong bộ phận điều khiển của riêng nó. Đến điểm này, N đã mô
phỏng xong một bước chuyển của M.
Chúng ta chọn cho làm kiểm trạng của N tất cả những trạng thái tương
ứng với một trong những kiểm trạng của M. Vì thế mỗi khi M kiểm nhận, N
cũng kiểm nhận và N không kiểm nhận gì khác với M.
Về tính hữu hạn: Một sai lầm thường gặp là lẫn lộn một giá trị luôn hữu
hạn tại một thời điểm bất kỳ với một tập giá trị hữu hạn. Phép xây dựng
máy đa băng thành một băng có thể giúp chúng ta định rõ sự khác biệt này.
Trong phép xây dựng đó, chúng ta đã dùng các rãnh trên băng để ghi nhận
vị trí của các đầu đọc-ghi. Vì sao chúng ta không thể lưu những vì trí này
như các số nguyên trong bộ phận điều khiển hữu hạn? Người ta có thể lập
luận một cách vô yù rằng sau n bước chuyển, máy Turing có thể có các vị
trí đầu đọc-ghi ở bên trong n vị trí của các vị trí đầu đọc-ghi ban đầu, và vì
thế chỉ phải lưu các số nguyên cho đến n.
Vấn đề là mặc dù các vị trí luôn hữu hạn, toàn bộ tập vị trí luôn vô hạn.
Nếu dùng trạng thái để lưu một vị trí đầu đọc-ghi nào đó thì phải có một
thành phần dữ liệu của trạng thái lưu một số nguyên làm giá trị. Thành phần
này buộc tập trạng thái phải vô hạn, ngay cả nếu chỉ có một số hữu hạn
trong chúng có thể dược dùng tại một thời điểm bất kỳ. Định nghĩa của một
máy Turing đòi hỏi rằng tập trạng thái phải hữu hạn. Vì thế chúng ta không
được phép lưu một vị trí ñaøu đọc-ghi trong bộ phận điều khiển hữu hạn.
Sự khác biệt giữa máy Turing đa băng và máy Turing đơn băng là máy
Turing đơn băng chỉ có một băng cho phép vô hạn hai đầu, có tập trạng thái
kết thúc và không có tình trạng dừng của đầu đọc viết ( không có S). Tuy
vậy người ta cũng chỉ ra rằng những khác biệt này không làm thay đổi lớp

c mt thut toỏn mi gii nú ch vi thi gian a thc. Cui cựng l nhng
bi toỏn thuc loi NP cha th phõn loi mt cỏch chớnh xỏc l thuc lp bi
toỏn cú phc tp a thc hay cú phc tp khụng a thc.
Gii c Khụng gii c phc tp khụng
phi a thc
Bi toỏn NP (cha phõn loi)
1. Lp P:
13
Gii c Khụng gii c
phc taùp
ủa thc
Phn loi cỏc bi toỏn
Định nghĩa 2: Lớp P là lớp các ngôn ngữ được đoán nhận bởi máy Turing đơn
định và độ phức tạp tính toán là đa thức.
Có thể phát biểu một cách khác là: một bài toán được coi là thuộc lớp P nếu
tồn tại một thuật toán đa thức để giải nó. Các bài toán thuộc lớp này có độ
phức tạp là O(n
k
) hoặc nhỏ hơn O(n
k
), như vậy các bài toán có độ phức tạp
hằng O(1), phức tạp tuyến tính O(n) và logarith O(nlog
a
n) đều là các bài toán
thuộc lớp đa thức.
Do có sự “Bùng nổ tổ hợp” khi chuyển từ hàm đa thức sang hàm mũ, các
thuật toán có độ phức tạp tính toán cấp từ đa thức trở xuống, thì hiện tại về

toán là T(n)=2
n
– 1. Với n bé khoảng 5 – 10, chương trình cho ra kết quả sau
vài phút tính toán, với n khoảng 10-15 chương trình chạy mất vài giờ, còn nếu
n tương đối lớn, ví dụ n=64 chương trình chạy khoảng 50 tyû năm!
Ta xét dưới đây các bài toán thuộc lớp sẽ được gọi là lớp NP.
2. Lớp NP:
Phần lớn lý thuyết độ phức tạp tính toán dựa trên các bài toán quyết định
(decision problem). Câu trả lời cho các bài toán này chỉ là yes (có hay đúng)
hoặc no (không hay sai). Câu trả lời cho mỗi bài toán quyết định tuỳ thuộc vào
từng dữ liệu cụ thể (instance) của bài toán đó. Bộ dữ liệu cho câu trả lời đúng
gọi là bộ dữ liệu yes (yes-instance), còn bộ dữ liệu cho câu trả lời sai gọi là bộ
dữ liệu no (no-instance).
Định nghĩa 3: Một bài toán được gọi là “nhận biết” nếu đó là bài toán mà các
kết quả chỉ có thể lập một trong hai giá trị Đúng hoặc Sai.
Ví dụ bài toán quyết định:
+ Chu trình Hamilton. Cho đồ thị vô hướng G=(N,E). Hỏi G có chứa chu
trình đi qua mọi đỉnh của đồ thị, mỗi đỉnh một lần hay không?
Nhiều bài toán tối ưu có các biến thể là một bài toán quyết định. Sau đây
là hai biến thể của bài toán qui hoạch tuyến tính và qui hoạch tuyến tính
nguyên:
+ Bất đẳng thức tuyến tính. Cho ma trận A ∈ Z
mxn
và vectô b ∈ Z
m
. Có hay
không vectô x ∈ Q
n
thoả mãn Ax ≤ b? (Z
n

liệu yes của nó phải có một chứng cứ (certificate) có thể kiểm tra trong thời
gian đa thức để kết luận được đó đúng là dữ liệu yes. (Để yù rằng trong định
nghĩa này ta không đòi hỏi phải có chứng cứ cho bõ dữ liệu no và không đòi
hỏi có thuật toán đa thức giải P).
Chẳng hạn, đối với bài toán chu trình Hamilton thì chứng cứ cho bõ dữ liệu
yes chỉ đơn giản là một chu trình Hamilton tương ứng với bộ dữ liệu đó, bởi vì
với chu trình đó ta có thể dễ dàng kiểm tra trong thời gian đa thức xem nó có
phải là hành trình đi qua mọi đỉnh của đồ thị, mỗi đỉnh một lần hay không?
Chúng ta đều biết rằng tính xác định là một trong ba đặc tính quan trọng
của thuật toán. Nghĩa là mỗi bước của thuật toán phải được xác định duy nhất
và có thể thực thi được. Nếu có sự phân chia trường hợp tại một số bước thì
thông tin tại bước đó phải đầy đủ để thuật toán có thể tự quyết định chọn lựa
trường hợp nào. Ta tạm gọi các thuật toán thoả mãn tính xác định là các thuật
toán tự quyết.
Vậy thì điều gì sẽ xảy ra nếu ta đưa ra một “thuật toán” có tính không tự
quyết? Nghĩa là tại một bước của “thuật toán”, ta đưa ra một số trường hợp
chọn lựa nhưng không cung cấp đầy đủ thông tin để “thuật toán” tự quyết
định? Thật ra, trong cuộc sống, những “thuật toán” thuộc loại này rất hay được
áp dụng. Chẳng hạn, ta có một lời chỉ dẫn khi đi du lịch: “Khi đi hết khu vườn
này, bạn hãy chọn một con đường mà bạn cảm thấy thích. Tất cả đều dẫn đến
bảo tàng lịch sử”. Nếu là khách du lịch, bạn sẽ cảm thấy bình thường. Nhưng
máy tính thì không! Nó không thể thực thi những hướng dẫn không rõ ràng
như vậy!
Đến đây, lập tức sẽ có một câu hỏi rằng “Tại sao lại đề cập đến những
thuật toán có tính không tự quyết dù máy tính không thể thực hiện một thuật
toán như vậy?”. Câu trả lời là, khi nghiên cứu về thuật toán không tự quyết, dù
không dùng để giải bài toán nào đi nữa, chúng ta sẽ có những hiểu biết về hạn
chế của những thuật toán tự quyết thông thường.
16
Đến đây, ta hãy xem sự khác biệt về độ phức tạp của một thuật toán tự

quyết tức là bài toán NP.
Như vậy bài toán người bán hàng rong là bài toán thuộc lớp NP. Cho đến
nay người ta chưa chứng minh được rằng tồn tại hay không một thuật toán tự
quyết có độ phức tạp đa thức cho bài toán người bán hàng rong. Vì vậy, bài
toán này (là một bài toán NP) chưa thể xếp được vào lớp đa thức hay không đa
17
thức. Do đó, lớp bài toán NP chưa thể phân loại là thuộc lớp đa thức hay
không.
Rõ ràng P⊆ NP, lớp bài toán NP cũng chứa những bài toán thuộc lớp đa
thức thực sự, bởi vì nếu một bài toán được giải bằng thuật toán tự quyết có độ
phức tạp đa thức thì chắc chắn khi dùng thuật toán không tự quyết cũng sẽ có
độ phức tạp đa thức. Nhưng không rõ liệu P = NP hay không? Có thể nói đây
là bài toán trung tâm trong lý thuyết độ phức tạp tính toán mà đến nay vẫn còn
là vấn đề mở, chưa được ai chứng minh hay bác bỏ. Ví dụ cụ thể cho vấn đề
này là bài toán bất đẳng thức tuyến nguyên và bài toán chu trình Hamilton, cả
hai thuộc NP, nhưng không biết chúng có thuộc P hay không?
Tên gọi NP là do từ “Nondeterministic Polynomial” (đa thức không đơn
định). Để giải thích điều này ta cần hiểu sơ qua thế nào là thuật toán không
đơn định thông qua máy Turing không đơn định: khi đọc mỗi kí hiệu bất kỳ
ở một trạng thái bất kỳ, máy được phép có một số khả năng hành động. Còn về
các yếu tố khác, một máy Turing không đơn định được định nghĩa như một
máy đơn định. Một từ ω được đoán nhận nếu nó sinh ra một tính toán đoán
nhận được, độc lập với việc nó cũng có thể sinh ra các tính toán khác dẫn đến
thất bại. Như vậy, khi quan hệ với các máy không đơn định, ta không quan tâm
đến mọi con đường dẫn đến thất bại nếu có một con đường có thể dẫn đến
thành công.
Thời gian cần thiết để máy Turing không đơn định M đoán nhận một từ ω
∈ T(M) được định nghĩa bằng số bước trong tính toán ngắn nhất của M dùng
để đoán nhận ω.
Định nghĩa 6: Lớp NP là lớp các ngôn ngữ được đoán nhận bởi các máy

ra từ họ này n/3 tập hợp từng đôi một rời nhau sao cho phủ được toàn bộ tập
hợp nền (nghĩa là hợp của chúng bằng tập hợp nền) hay không?
19