NP-Completeness
NP-Completeness
Nhóm 8:
Hoàng Trần Thy Ngọc
Nguyễn Duy Thành
Trương Thị Ty
Thuật toán thời gian đa thức
Thuật toán thời gian đa thức
•
Thuật toán giải một bài toán cụ thể trong thời gian
O(T(n)) nếu: mỗi đầu vào i có độ dài n, thuật toán
cho kết quả trong thời gian là O(T(n)).
•
Một bài toán cụ thể giải được trong thời gian đa
thức nếu tồn tại thuật toán giải nó trong thời gian
O(n
k
), k hằng số.
Ngôn ngữ
Ngôn ngữ
Bảng chữ cái A là tập hữu hạn các ký tự.
Ví dụ: A = {0,1}
Từ là 1 dãy các chữ cái của A.
Một ngôn ngữ L trên A là 1 tập các từ trên A.
Ví dụ: L={00, 01, 10, 11}
Từ rỗng: ε
Ngôn ngữ rỗng: Ø
Ngôn ngữ gồm tất cả các từ trên A: A*
Bài toán - ngôn ngữ
Bài toán - ngôn ngữ
E = {0,1}.

Bài toán quyết đinh Q 
Ngôn ngữ L = {x Є E*: Q(x) = 1}
•
Thuật toán A chấp nhận một từ x Є E*: nếu với
đầu vào x, A cho kết quả A(x) = 1.
•
A loại bỏ x nếu A(x) = 0.
•
Ngôn ngữ L được chấp nhận bởi A:
L={x Є E*: A(x)=1}
–
L được chấp nhận bởi A trong thời gian đa thức nếu có
hằng k sao cho mọi từ x có độ dài n được A chấp nhận
trong thời gian O(n
k
)
Ngôn ngữ được quyết định
Ngôn ngữ được quyết định
•
Một ngôn ngữ L được quyết định bởi
thuật toán A nếu:
–
x thuộc L  A chấp nhận x
–
x không thuộc L  A loại bỏ x.
•
L được quyết định bởi A trong trong
thời gian đa thức nếu có hằng số k sao
cho mọi từ x có độ dài n được A quyết
định trong thời gian O(n

k
)
Lớp P
Lớp P
•
Định nghĩa: Lớp P bao gồm tất cả các bài toán
giải được bởi thuật toán đơn định trong thời gian
đa thức (tức là tồn tại thuật toán giải quyết nó với
thời gian chạy đa thức).
–
thuật toán đơn định (deterministic algorithm): là thuật
toán có kết quả thực hiện mỗi phép toán được xác định
duy nhất.
•
P = {L ngôn ngữ trên E: có thuật toán A quyết
định L trong thời gian đa thức}
•
Định lý: P = {L ngôn ngữ trên E: có thuật toán A
chấp nhận L trong t.g.đ.t.}
Thuật toán kiểm chứng
Thuật toán kiểm chứng
•
Thuật toán kiểm chứng A: là một thuật toán gồm
hai biến, một biến bình thường là một xâu nhị
phân đầu vào x, và một biến là xâu nhị phân y
(được gọi là xâu kiểm chứng).
•
Thuật toán A kiểm chứng x nếu tồn tại xâu kiểm
chứng y để A(x,y) =1.
•

Ngôn ngữ L được kiểm chứng bởi A là:
L = {x Є E*: tồn tại y Є E*: A(x,y)=1 }
Lớp NP
Lớp NP
•
Định nghĩa: Lớp NP bao gồm tất cả các bài toán có thể giải được bởi
thuật toán không đơn định trong thời gian đa thức
–
Thuật toán không đơn định (nondeterministic algorithm): là thuật toán
có kết quả không phải là một giá trị được xác định duy nhất mà là một tập
hữu hạn các giá trị.
•
Lớp NP là lớp các ngôn ngữ được kiểm chứng trong thời gian đa thức.
•
L Є NP  tồn tại thuật toán 2 biến thời gian đa thức A và hằng số c
sao cho:
L= {x Є E*: tồn tại y Є E*, |y|=O(|x|
c
): A(x,y)=1}
Ta nói: A kiểm chứng L trong thời gian đa thức
•
Dễ dàng nhận thấy P
⊆
NP.
•
Khi nào mà P = NP ????
Lớp co-NP
Lớp co-NP
-
L Є co-NP  Σ*\L Є NP

-
4 trường hợp có thể xảy ra:
Phép quy dẫn (Reducibility)
Phép quy dẫn (Reducibility)
•
Ngôn ngữ L1 qui dẫn được về ngôn ngữ L2 trong
thời gian đa thức (Ký hiệu: L1 ≤p L2) nếu tồn tại
một hàm f tính được trong thời gian đa thức.
f: E* -> E* sao cho x Є L1

f(x) Є L2
f: được gọi là hàm quy dẫn
Lớp NP- đầy đủ (NP-completeness)
Lớp NP- đầy đủ (NP-completeness)
•
Ngôn ngữ L là NP-đầy đủ (Ký hiệu:
NPC) nếu:
1. L Є NP
2. Với mọi L’ Є NP thì L’ ≤p L.
•
Ngôn ngữ L là NP-khó (NP-hard) nếu
L thỏa mãn điều kiện 2 (nhưng không
nhất thiết thoả điều kiện 1).
P vs NP
P vs NP
•
Định lý: Nếu có một bài toán NP-đầy đủ
nào giải được trong t.g.đ.t. thì P = NP.
Nếu có một bài toán trong NP nào mà
không giải được trong t.g.đ.t. thì tất cả các

bài toán NP-đầy đủ đều không giải được
trong t.g.đ.t.
Chứng minh tính NP-đầy đủ
Chứng minh tính NP-đầy đủ
•
Bổ đề: Nếu L là một ngôn ngữ sao cho L’ ≤p L với L’ Є
NPC, thì L là NP-khó. Hơn nữa, nếu L Є NP thì L Є NPC.
•
Để chứng minh L Є NPC:
- Chứng minh L Є NP
- Chọn một ngôn ngữ L’ Є NPC
- Tìm f: E* > E* , x Є L’ , y Є L
x > f(x) = y
- Chứng minh f thỏa mãn: x Є L’  f(x) Є L với mọi x Є Σ*
- Tìm thuật toán F để tính hàm quy dẫn f và chứng minh F chạy trong
thời gian đa thức
Circuit satisfiability
Circuit satisfiability
•
Phần tử bool (Boolean combinational element) là
các phần tử có đầu vào và ra thuộc {0,1} (0: sai, 1:
đúng)
–
Một phần tử bool dùng để tính 1 hàm boolean đơn,
được gọi là một cổng logic (logic gate).
•
Mạch bool (Boolean combinational circuit) xây
dựng từ các phần tử bool, được nối với nhau bằng
các dây (wire).
Circuit satisfiability

Circuit satisfiability
•
3 cổng logic cơ bản: cổng NOT, cổng AND và
cổng OR (Cổng vào x và y, cổng ra z)
•
Đầ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:

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.

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.
Circuit satisfiability
Circuit satisfiability
Ví dụ
Ví dụ
•
Bài toán Circuit satisfiability: “Cho một mạch bool gồm
các cổng AND, OR, NOT; nó có thỏa mãn hay không ?”
•
Độ dài của mạch là số các phẩn tử tổ hợp bool + số các dây
CIRCUIT-SAT
CIRCUIT-SAT
•
Định nghĩa:

CIRCUIT-SAT= {<C>: C có thể thỏa được một
mạch bool}
<C> là chuỗi nhị phân được ánh xạ từ mạch C.
•
Bổ đề: CIRCUIT-SAT Є NP
•
Bổ đề: CIRCUIT-SAT là NP-khó
•
Định lý: CIRCUIT-SAT Є NP-đầy đủ
SAT
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
•
Một công thức Φ là satisfiable (thỏa mãn được) nếu có một
phép gán giá trị để giá trị ra của Φ là 1.
SAT = {<Φ>: Φ là một công thức thỏa mãn được}
•
Định lý: SAT Є NP-đầy đủ
3-CNF SAT
3-CNF SAT
•
1 literal trong một công thức boolean là một biến x
hoặc ¬x.
•

1 công thức boolean là có dạng hợp chuẩn
(conjunctive normal form, CNF), nếu nó được
biểu diễn như là một phép AND của các mệnh đề,
mỗi mệnh đề là một phép OR của các literal.
•
1 công thức boolean là một dạng 3-CNF nếu mỗi
mệnh đề của nó có đúng 3 literal khác nhau.
•
3-CNF-SAT={Ф Є 3-CNF, Ф là công thức thoả
mãn được}
•
Định lý: 3-CNF-SAT Є NP-đầy đủ
NP-complete problems
NP-complete problems
•
Muốn chứng minh một bài toán thuộc lớp NP-đầy đủ đều
được quy về từ NP-đầy đủ của CIRCUIT-SAT.
Bài toán clique
Bài toán clique
•
Một Clique trong một đồ thị vô hướng G = (V, E), 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’|).
•
Bài toán clique: Tìm một clique có kích thước lớn nhất
trong một đồ thị cho trước.
•
Giả sử tồn tại số k là kích thước của một clique trong đồ
thị G ta định nghĩa:

CLIQUE = {(G, k): G là một đồ thị với một clique có kích thước k}.
•
Đã chứng minh được: CLIQUE Є NP-đầy đủ
Bài toán vertex-cover
Bài toán vertex-cover
•
Một vertex cover trong một đồ thị vô hướng G = (V, E),
V’ V, nếu cạnh (u, v) E thì u V’ hoặc v V’ (hoặc ⊆ ∈ ∈ ∈
cả 2). Kích thước của vertex cover là số đỉnh nó chứa (=|
V’|).
•
Bài toán vertex-cover: là tìm một vertex cover có kích
thước nhỏ nhất trong một đồ thị cho trước.
•
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}.
•
Đã chứng minh được: VERTEX-COVER Є NP-đầy đủ
CLIQUE quy về VERTEX-COVER
CLIQUE quy về VERTEX-COVER
•
Hình (a) là một đồ thị vô hướng G = (V,E) với clique V’ =
{u,v,x,y}. Hình (b) là phần bù của đồ thị G được sinh ra
bởi thuật toán rút gọn, có vertex cover V – V’ = {w, z}
Bài toán chu trình Hamilton
Bài toán chu trình Hamilton
•
Cho đồ thị vô hướng G=(V,E), một chu trình Hamilton

trong G là một chu trình đơn và đi qua tất cả các đỉnh của
G (qua mỗi đỉnh đúng một lần, trừ đỉnh đầu trùng đỉnh
cuối).
•
Đồ thị G được gọi là đồ thị Hamilton nếu nó có chu trình
Hamilton, nếu không nó được gọi là đồ thị không phải
Hamilton.
•
Bài toán chu trình Hamilton: đồ thị G có chu trình
Hamilton hay không ?
•
HAM-CYCLE = {<G>: G là đồ thị Hamilton}
•
Đã chứng minh được: HAM-CYCLE Є NP-đầy đủ