TIU LUN MÔN HỌC

PHÂN TÍCH THIẾT KẾ THUT TOÁN.

Đề tài: LỚP BÀI TOÁN NPC
(Nondeterministic Polynomial Completeness)

Giảng viên hướng dẫn : TS. Hoàng Quang
Thành viên thực hiện : Nhóm 7

1. Trần Lê Ngọc ([email protected])
2. Huỳnh Quốc Lực ([email protected])
3. Trần Thị Hạnh ([email protected])
4. Võ Thị Tình ([email protected])
5. Nguyễn Thị Bích Liên ([email protected])
NỘI DUNG
• Phân loại bài toán
• Lớp bài toán P
• Lớp bài toán NP
• Lớp bài toán NPC
• Một số bài toán thuộc lớp NPC

2
Phân loại bài toán
Bài toán
Giải được
Không giải
được
Lớp không đa
thức

với một độ lớn dữ liệu đầu vào nhất định.
5
Ví dụ: Cho một tập hợp có n phần tử, hãy liệt kê tất cả các
tập con khác trống của tập hợp này.
Số tập con của một tập
hợp có n phần tử là 2
n
-
1. Lời giải tuy đã có
nhưng khi thể hiện lời
giải này bằng bất kỳ
thuật toán nào thì phải
tốn ít nhất 2
n
-1 bước.
N
Số lần thực
hiện
Ghi chú
16 Khoảng vài
chục ngàn
Máy tính có thể giải
32 Khoảng 4 tỷ Cần những máy
tính tốc độ cao và
tốn rất nhiều thời
gian
33 Khoảng 8 tỷ
Lớp bài toán NP (Nondeterministic
Polynomial time)
• Chúng ta đều biết rằng tính xác định là một trong

??? Choose(1,2,3);
Go(“Viện bảo tàng);
Khi nghiên cứu về thuật toán không đơn định,
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 đơn định thông thường.
2
Ví dụ 2: Bài toán người bán hàng (TSP)
- Có một người giao hàng cần đi giao hàng tại n thành phố.
- Xuất phát từ một thành phố nào đó, đi qua các thành phố khác để
giao hàng và trở về thành phố ban đầu.
- Mỗi thành phố chỉ đến một lần
- Khoảng cách từ một thành phố đến các thành phố khác là xác định.
Hãy tìm một chu trình sao cho tổng độ dài các cạnh nhỏ hơn M?
Lớp bài toán NP …
- Liệt kê từng con đường có thể đi
- So sánh chiều dài mỗi con đường
tìm được với M
+ Tìm được một con đường phù hợp
+ Xét hết tất cả các con đường
- Chọn một con đường có thể và
tính chiều dài của nó.
- So sánh chiều dài này với M
+ Nếu <=M thì báo là thành công
+ Ngược lại báo chọn lựa sai
- Dùng thuật toán đơn định  độ phức tạp không thuộc lớp đa thức
- Dùng thuật toán không đơn định  độ phức tạp đa thức
8
Lớp bài toán NP …
9

(thuật toán không đơn định), nhưng chưa
tìm ra được một lời giải hữu hiệu chạy trên
máy thông thường (thuật toán đơn định) để
giải chúng).
Những bài toán NP này lại thêm một tính
chất nữa là: “Nếu bất kỳ một trong những
bài toán này có thể giải được trong thời
gian đa thức thì tất cả những bài toán thuộc
lớp NP cũng sẽ được giải trong thời gian đa
thức trên một máy đơn định”.
Những
bài toán
như vậy
được
gọi là
lớp bài
toán NP
đầy đủ
(NPC).
Lớp NPC …
11
Định nghĩa: Chúng ta nói L là bài toán thuộc lớp NPC nếu các
khẳng định dưới đây đều đúng:
1. L Є NP
2. Với mọi L’ Є NP thì L’ ≤ pL (Với mọi ngôn ngữ L’ thuộc
NP, có một phép thu thời gian đa thức từ L’ về L).
(Nếu L chỉ thoã điều kiện 2 thì L thuộc lớp NP-Khó)
Định lý:
Nếu có một bài toán NPC nào giải được trong thời gian đa
thức thì P = NP.

hiệu L
1


L
2
) nếu bất kỳ giải thuật nào giải được L
2
thì
cũng có thể được dùng để giải L
1
.
Bổ đề:
Để chứng minh một bài toán mới L là NPC chúng ta
cần chứng minh:
1. L thuộc lớp NP
2. Một bài toán L’ Є NPC đã biết thì L’ thu giảm
được về L
• Giả sử ta biết HCP là NPC và muốn xác định xem TSP có là NPC
hay không?
• Bất kỳ giải thuật nào có thể dùng để giải TSP cũng có thể dùng để
giải HCP thông qua sự thu giảm sau: Cho G=(V,E) là một thể hiện
của HCP, tạo ra một thể hiện của TSP tương ứng G’=(V,E’), trong
đó:
– Các thành phố trong TSP tương ứng tập đỉnh trong HCP
– Khoảng cách giữa hai thành phố ta gán giá trị:
0 nếu (i,j)  E
1 nếu (i,j)  E
một chu trình hamilton trong G.
• Nghĩa là HCP thu giảm về TSP  Tính chất NPC của
HCP bao hàm tính chất NPC của TSP. Hay TSP là bài
toán NPC

1
2
5
4
3
1
2
5
4
3
0
0
0
0
0
0
G=(V,E) của HCP
G’=(V,E’) của STP
1
1
1
1
Định lý Cook
Bài toán thoả mạch logic (circuit satisfiability problem-
CSP):

x y X v y
0 0 0
0 1 1
1 0 1
1 1 1
x
y
z
x
y
z
Bài toán CSP …
• Đầu vào (Circuit input): các dây không nối với một
phần tử vào nào
• Đầu ra (Circuit output): các dây không nối với một
phần tử ra nào
• Ta xét các mạch (circuit) chỉ có một đầu ra:
1. Một phép gán giá trị của một mạch là một tập các giá trị
đầu vào.
2. Một mạch là thỏa mãn (satisfiable) nếu có một phép gán
giá trị đầu vào sao cho đầu ra của mạch là 1.
• Bài toán CSP là xác định xem có tồn tại một phép
gán các trị logic vào các biến logic sao cho toàn
công thức trở thành đúng (đầu ra là 1).
17
Định lý Cook …
Bài toán CSP …
Ví dụ:
toán NPC. Định lý Cook: “Nếu tồn tại một giải thuật thời gian đa
thức để giải bài toán thoả mãn mạch logic thì tất cả mọi
bài toán trong lớp NP có thể giải được trong thời gian đa
thức”
Một số bài toán NPC
• Hàng nghìn bài toán khác nhau được biết là
NPC.
20
CIRCUIT-SAT
SAT
3-CNF-SAT
CLIQUE
VERTEX-COVER
HAM-CYCLE
TSP
SUBSET-SUM
Bài toán thỏa được công thức - SAT
• Một trạng thái của bài toán SAT là một công
thức boolean Φ gồm:
1. Các biến boolean: x1, x2, …
2. Các liên kết boolean: các hàm boolean một hoặc hai
biến: AND, OR, NOT, , 
3. Các dấu ngoặc tròn để nhóm các toán tử và toán
hạng nếu cần làm thay đổi thứ bậc (độ ưu tiên) của

 (x
7
 (x
1
 x
2
 x
4
))
 (x
8
 (x
5
 x
6
))
 (x
9
 (x
6
 x
7
))
 (x
10
 (x
7
 x
8
 x

)  (x
3
 x
2
 x
4
)  ( x
1
 
x
3
  x
4
)
• 3-CNF SAT là NPC
• Để chứng minh vấn đề này chúng ta chứng tỏ:
– 3-CNF SAT  NP
– SAT  p 3-CNF SAT 23
Bài toán clique
• Một Clique trong một đồ thị vô hướng G = (V, E)
là một tập con V’ ⊆ V, mỗi cặp đỉnh trong V’ đều
có cạnh E. Hay nói cách khác, clique là một đồ thị
con đầy đủ của G. Kích thước của clique là số
đỉnh nó chứa (=|V’|).

• Giả sử tồn tại số k là kích thước của một
vertex cover trong đồ thị G ta định nghĩa:
VERTEX-COVER = {(G, k): G là một đồ thị với một
vertex cover có kích thước k}.
• VERTEX-COVER là NPC
25
G=(V,E)
u
z
v
w
y
x
u
z
v
w
y
x
G’