The theory of NP-Completeness 1
CHUYÊN ĐỀ: LÝ THUYẾT ĐỘ PHỨC TẠP
THUẬT TOÁN
LÝ THUYẾT NP - ĐẦY ĐỦ
(THE THEORY OF NP - COMPLETENESS)
Giáo viên : Thầy Vũ Đình Hoà
The theory of NP-Completeness 2
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
7. Thuyết Cook
The theory of NP-Completeness 3
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
hợp D
∏
các thể hiện và tập con Y
∏
⊆ D

có chứa một đồ thị con G
1
’ mà G
1
’
đẳng cấu với đồ thị G
2
hay không?
The theory of NP-Completeness 5

Giải thích về đồ thị đẳng cấu:
G
1
’ đẳng cấu với G
2
nếu như có |V
1
’| = |V
2
|, |E
1
’| = |E
2
| và
ở đó tồn tại một song ánh f : V
2
 V
1
’ sao cho {u,v} ∈
E


Question: tồn tại hay không một đường đi nào qua tất cả
các thành phố trong C mà có tổng độ dài không lớn hơn
B? (Tồn tại một sắp thứ tự sao cho
)
1. BÀI TOÁN QUYẾT ĐỊNH
)()2()1(
, ,,
m
CCC
πππ
BCCdCCd
m
m
i
ii
≤+
∑
−
=
+
),()),((
)1()(
1
1
)1()(
ππππ
The theory of NP-Completeness 7

Một bài toán quyết định có thể được chuyển hoá từ một

thể biểu diễn ∑* là tập hợp tất cả các xâu hữu hạn các kí
hiệu lấy từ tập ∑.

Nếu L là một tập con của ∑*, chúng ta nói rằng L là
một ngôn ngôn ngữ trên tập các chữ cái của ∑.
The theory of NP-Completeness 10

Ví dụ:
Nếu ∑ = {0, 1}, khi đó I* = {ε, 0, 1, 01, 10, 11, 000, 001,… }
Khi đó {01,001,111,1101010} là một ngôn ngữ trên tập {0,1}

Sự tương ứng giữa bài toán quyết định và ngôn ngữ được dẫn
đến bởi các lược đồ mã hoá.

Một lược đồ mã hoá e cho bài toán ∏ cung cấp một cách thức
miêu tả mỗi sự kiện của ∏ bằng một xâu thích hợp các ký
hiệu trên tập chữ cái cố định ∑.
2. NGÔN NGỮ VÀ LƯỢC ĐỒ MÃ HÓA
The theory of NP-Completeness 11

Bài toán ∏ và lược đồ mã hoá e cho ∏ chia ∑* thành 3 lớp:
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.
Ngôn ngữ: L[∏, e] = {x ∈ ∑* với ∑ được sử dụng bởi e, và x
mã hóa một thể hiện I ∈ Y
π
bằng e}


Nếu x
1
, x
2
, , x
m
là các xâu có cấu trúc biểu diễn các đối
tượng X
1
,X
2
, …, X
m
, khi đó (x
1
, …, x
m
) là một xâu có
cấu trúc biểu diễn chuỗi (X
1
,…,X
m
)
2. NGÔN NGỮ VÀ LƯỢC ĐỒ MÃ HÓA
The theory of NP-Completeness 15

Các biểu diễn cho 4 kiểu đối tượng như sau:

Một tập các đối tượng được biểu diễn bởi thứ tự các phần

x
i
là xâu có cấu trúc biểu diễn U
i
và y
i
là xâu có cấu trúc
biểu diễn f(U
i
) ∈ W, 1 ≤ i ≤ m.

Một số hữu tỉ q được biểu diễn bởi một xâu có cấu 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.
2. NGÔN NGỮ VÀ LƯỢC ĐỒ MÃ HÓA
The theory of NP-Completeness 17
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
các ô vuông có đánh các nhãn là:… -3, -2, -1, 0, 1, 2, 3…
3. MÁY TURING TẤT ĐỊNH VÀ LỚP P
The theory of NP-Completeness 18
- 3 - 2 - 1 0 1 2 3 4
Bộ điều khiển
trạng thái
hữu hạn
Đầu đọc ghi

Hàm chuyển trạng thái: δ cho phép với mỗi trạng thái của
máy và một kí kiệu đọc được từ ô trống đối diện, ta xác
định được:

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
2. MÁY TURING TẤT ĐỊNH VÀ LỚP P
The theory of NP-Completeness 21
3.1. Miêu tả máy Turing tất định

Quá trình thực hiện của DTM
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: …
3. MÁY TURING TẤT ĐỊNH VÀ LỚP P
The theory of NP-Completeness 22
2.1. Miêu tả máy Turing tất định

Quá trình thực hiện của DTM
2. Các bước tính toán: …
- Đọc kí tự đối diện với đầu đọc
- 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

x = “10100”
3. MÁY TURING TẤT ĐỊNH VÀ LỚP P
The theory of NP-Completeness 25

Hàm trạng thái cho trong bảng:
3. MÁY TURING TẤT ĐỊNH VÀ LỚP P