Bài giảng Giải thuật - Chương 12: NP đầy đủ

ùc cạnh của E và tạo nên một chu trình hay không. 
Thời gian chạy: O ( n 2 ). 
13.11.2004 
23 
Ch. 12: NP-Completeness 
Giải thuật chứng thực 
Ta định nghĩa một giải thuật chứng thực (verification algorithm) là một giải thuật A có hai đối số (two-argument algorithm), trong đó một đối số là một chuỗi input thông thường x và đối số kia là một chuỗi nhị phân y , y được gọi là một chứng thư (certificate) . 
 Ngôn ngữ được chứng thực bởi một giải thuật chứng thực A là 
L = { x  { 0, 1 } * : tồn tại y  { 0, 1 } * sao cho A ( x , y ) = 1 }. 
Ví dụ: Trong bài toán chu trình hamilton, chứng thư là danh sách của các đỉnh trong chu trình hamilton. 
13.11.2004 
24 
Ch. 12: NP-Completeness 
Lớp NP 
 Lớp NP (NP: “ n ondeterministic p olynomial time”) là lớp các ngôn ngữ có thể được chứng thực bởi một giải thuật thời gian đa thức. Chính xác hơn: 
Cho một ngôn ngữ L . 
Ngôn ngữ L thuộc về NP 
 
Tồn tại một giải thuật thời gian đa thức hai đối số A cùng với một hằng số c sao cho 
L = { x  { 0, 1 } * : tồn tại một chứng thư y với độ dài  y  = O ( x  c ) sao 	 cho A ( x , y ) = 1 }. 
Ta nói rằng giải thuật A chứng thực ngôn ngữ L trong thời gian đa thức . 
13.11.2004 
25 
Ch. 12: NP-Completeness 
Lớp NP 
Ví dụ: HAM-CYCLE  NP. 
13.11.2004 
26 
Ch. 12: NP-Completeness 
Tính có thể rút gọn được (reducibility) 
Làm thế nào để so sánh “ độ kho ù” của các bài toán? 
Ví dụ 
Bài toán Q : Giải phương trình bậc nhất ax + b = 0 
Bài toán Q’ : Giải phương trình bậc hai px 2 + qx + r = 0 
Giải phương trình bậc nhất ax + b = 0 bằng cách giải phương trình bậc hai: 0 x 2 + ax + b = 0. 
Ta nói: 
Bài toán Q “ có thể rút gọn được ” về bài toán Q’ bằng cách biểu diễn phương trình bậc nhất dưới dạng: 0 x 2 + qx + r = 0 . 
Q là “ không khó hơn ” Q’. 
Điều kiện: thời gian để rút gọn bài toán “không được lâu hơn” thời gian để giải chính bài toán đó. 
13.11.2004 
27 
Ch. 12: NP-Completeness 
Tính có thể rút gọn được (tiếp) 
Một ngôn ngữ L 1 là có thể rút gọn được trong thời gian đa thức ve à một ngôn ngữ L 2 , ký hiệu L 1  P L 2 , nếu tồn tại một hàm có thể tính được trong thời gian đa thức f : { 0, 1 } *  { 0, 1 } * sao cho với mọi x  { 0, 1 } * , 
x  L 1  f ( x )  L 2 . 
Ta gọi hàm f là hàm rút gọn (reduction function). 
13.11.2004 
28 
Ch. 12: NP-Completeness 
Tính có thể rút gọn được (tiếp) 
Nhận xét:  x  {0,1} * , trả lời “ x  L 1 ?” bằng cách trả lời “ f ( x)  L 2 ?” 
khi f ( x)  L 2 thì x  L 1 
khi f ( x)  L 2 thì x  L 1 
{0,1} * 
{0,1} * 
L 1 
L 2 
f 
x 
f ( x ) 
13.11.2004 
29 
Ch. 12: NP-Completeness 
Tính có thể rút gọn được (tiếp) 
Một giải thuật thời gian đa thức F tính f được gọi là một giải thuật rút gọn (reduction algorithm). 
13.11.2004 
30 
Ch. 12: NP-Completeness 
Rút gọn trong thời gian đa thức 
Lemma 36.3 
L 1 , L 2  { 0, 1 } * là các ngôn ngữ sao cho L 1  P L 2 
 
Nếu L 2  P thì L 1  P . 
13.11.2004 
31 
Ch. 12: NP-Completeness 
NP-đầy đủ 
Một ngôn ngữ L  { 0, 1 } * là NP-đầy đủ (NP-complete) nếu 
1 . L  NP 
2. L’  P L với mọi L’  NP. 
Một ngôn ngữ L  { 0, 1 } * là NP-kho ù (NP-hard) nếu tính chất 2 ở trên được thỏa (trong khi tính chất 1 không nhất thiết phải được thỏa.) 
“Mọi bài toán trong NP đều không khó hơn bài toán L ” 
Ta định nghĩa NPC là lớp các ngôn ngữ NP-đầy đủ. 
“NPC là lớp các bài toán khó nhất trong NP” 
13.11.2004 
32 
Ch. 12: NP-Completeness 
NP-đầy đủ (tiếp) 
Định lý 36.4 
Nếu có bất ky ø một bài toán NP-đầy đủ nào có thể giải được trong thời gian đa thức, thì P = NP. 
Tương đương như thế: 
Nếu có bất kỳ một bài toán nào trong NP là không thể giải được trong thời gian đa thức, thì không có bài toán NP-đầy đủ nào là giải được trong thời gian đa thức. 
13.11.2004 
33 
Ch. 12: NP-Completeness 
Bài toán thỏa mãn mạch 
Cổng logic 
Mạch tổ hợp bool 
x 
z 
x 
y 
x 
y 
z 
z 
Cổng NOT 
Cổng AND 
Cổng OR 
x 1 
x 2 
x 3 
x 4 
x 5 
x 6 
x 7 
x 8 
x 9 
x 10 
13.11.2004 
34 
Ch. 12: NP-Completeness 
Bài toán thỏa mãn mạch (tiếp) 
Tính chất thỏa mãn mạch 
Một cách gán trị bool (truth assignment) cho một mạch tổ hợp bool là một tập các trị input bool 
Một mạch tổ hợp bool với chỉ một output là có thể thoả mãn được (satisfiable) nếu nó có một cách gán thỏa mãn (satisfying assignment), tức là một cách gán trị bool khiến cho output của mạch là 1. 
x 1 
x 2 
x 3 
x 4 
x 5 
x 6 
x 7 
x 8 
x 9 
x 10 
1 
1 
0 
1 
0 
0 
1 
1 
1 
1 
1 
13.11.2004 
35 
Ch. 12: NP-Completeness 
Bài toán thỏa mãn mạch (tiếp) 
 Bài toán thỏa mãn mạch là “Cho một mạch tổ hợp bool tạo bởi các cổng AND, OR, và NOT, nó có thể thỏa mãn được không?” 
CIRCUIT-SAT = {  C  : C là một mạch tổ hợp bool có thể thỏa mãn được }. 
Lemma 36.5 
Bài toán thỏa mãn mạch thuộc về lớp NP. 
Lemma 36.6 
Bài toán thỏa mãn mạch là NP-khó. 
Theorem 36.7 
Bài toán thỏa mãn mạch là NP-đầy đủ. 
13.11.2004 
36 
Ch. 12: NP-Completeness 
Cách chứng minh NP-đầy đủ 
Lemma 36.8 
Nếu L là một ngôn ngữ sao cho L’  P L với một L’  NPC, thì L là NP-khó. Thêm vào đó, nếu L  NP, thì L  NPC. 
13.11.2004 
37 
Ch. 12: NP-Completeness 
Bài toán thỏa mãn biểu thức bool 
 Biểu thức bool 
 = (( x 1  x 2 )  (( x 1  x 3 )  x 4 ))   x 2 
Một cách gán trị bool (truth assignment) cho một biểu thức bool  là một tập các trị cho các biến của  . 
Một cách gán thoả mãn (satisfying assignment) là một cách gán trị bool khiến cho biểu thức bool có trị là 1. 
Một biểu thức bool có một cách gán thỏa mãn gọi là một biểu thức có thể thỏa mãn được . 
 Bài toán thỏa mãn biểu thức bool 
SAT = {    :  là biểu thức bool có thể thỏa mãn được }. 
Theorem 36.9 
Bài toán thỏa mãn biểu thức bool là NP-đầy đủ. 
13.11.2004 
38 
Ch. 12: NP-Completeness 
Bài toán thỏa mãn biểu thức bool dạng 3-CNF 
 Biểu thức bool dạng 3-CNF ( 3 - c onjunctive n ormal f orm) 
 = ( x 1   x 1   x 2 )  ( x 3  x 2  x 4 )  ( x 1   x 3   x 4 ) 
 Bài toán thỏa mãn biểu thức bool dạng 3-CNF 
3-CNF-SAT = {    :  là biểu thức bool dạng 3-CNF có thể thỏa mãn được }. 
Theorem 36.9 
Bài toán thỏa mãn biểu thức bool dạng 3-CNF là NP-đầy đủ. 
13.11.2004 
39 
Ch. 12: NP-Completeness 
Bài toán clique 
Các định nghĩa 
Một clique của một đồ thị vô hướng G = ( V , E ) là một đồ thị con đầy đu û của G . 
 Kích thước của một clique là số đỉnh mà nó chứa. 
13.11.2004 
40 
Ch. 12: NP-Completeness 
Bài toán clique (tiếp) 
 Bài toán clique là bài toán tối ưu tìm clique có kích thước lớn nhất của một đồ thị. 
Bài toán quyết định tương ứng với bài toán clique là 
CLIQUE = {  G , k  : G là một đồ thị có một clique có kích thước k }. 
Theorem 36.11 
Bài toán clique là NP-đầy đủ. 
13.11.2004 
41 
Ch. 12: NP-Completeness 
Bài toán che phủ đỉnh 
Các khái niệm cơ bản 
Một che phu û đỉnh (vertex cover) của một đồ thị vô hướng G = ( V , E ) là một tập con V’  V sao cho nếu ( u , v )  E thì u  V’ hoặc v  V’ (hoặc cả hai). 
 Kích thước của một che phủ đỉnh là số đỉnh trong đó. 
13.11.2004 
42 
Ch. 12: NP-Completeness 
Bài toán che phủ đỉnh (tiếp) 
 Bài toán che phủ đỉnh là tìm một che phủ đỉnh có kích thước nhỏ nhất trong một đồ thị cho trước. 
Bài toán quyết định tương ứng dưới dạng một ngôn ngữ là: 
VERTEX-COVER = {  G , k  : đồ thị G có một che phủ đỉnh có kích 	thước k }. 
Theorem 36.12 
Bài toán che phủ đỉnh là NP-đầy đủ. 
13.11.2004 
43 
Ch. 12: NP-Completeness 
Bài toán tổng của tập con 
Cho một tập hữu hạn S  N và một trị đích t  N . 
 Bài toán tổng của tập con là hỏi có tồn tại một tập con S ’ S sao cho tổng các phần tử của nó bằng t hay không. 
Ví dụ: với S = {1, 3, 5, 7, 11, 13}, và t = 12 thì tập con S’ = {1, 11} là một lời giải. 
Bài toán tổng của tập con dưới dạng một ngôn ngữ: 
SUBSET-SUM = {  S , t  : tồn tại một tập con S ’ S sao cho 
 t =  s  S ’ s }. 
Theorem 36.13 
Bài toán tổng của tập con là NP-đầy đủ. 
13.11.2004 
44 
Ch. 12: NP-Completeness 
Bài toán chu trình Hamilton 
Bài toán chu trình Hamilton 
HAM-CYCLE = {  G  : G là một đồ thị hamilton } 
Theorem 36.14 
Bài toán chu trình hamilton là NP-đầy đủ. 
13.11.2004 
45 
Ch. 12: NP-Completeness 
Bài toán người bán hàng rong 
Các khái niệm cơ bản 
Cho một đồ thị đầy đu û G . Mỗi cạnh ( i , j ) nối hai đỉnh i và j của G có một chi phí là một số nguyên c ( i , j ) 
Ta định nghĩa một tua (tour) là một chu trình hamilton của G , chi phí của tua là tổng của các chi phí của mỗi cạnh của tua. 
13.11.2004 
46 
Ch. 12: NP-Completeness 
Bài toán người bán hàng rong (tiếp) 
 Bài toán người bán hàng rong (TSP, t ravelling- s alesperson p roblem) là tìm một tua có chi phí nhỏ nhất. 
Ngôn ngữ hình thức cho bài toán quyết định tương ứng là 
TSP = {  G , c , k  : G = ( V , E ) là một đồ thị đầy đu û, 
 c là một hàm số V  V  Z , 
 k  Z , và 
 G có một tua với chi phí  k }. 
Theorem 36.15 Bài toán người bán hàng rong là NP-đầy đủ. 
13.11.2004 
47 
Ch. 12: NP-Completeness 
P  NP? 
Bài toán mở quan trọng nhất trong khoa học máy tính lý thuyết. 
13.11.2004 
48 
Ch. 12: NP-Completeness