Chương 3: Chứng minh các kết quả của bài toán NP_đầy đủ

Giảng viên : PSG.TSKH.Vũ Đình Hòa

Chương 3: Chứng minh các kết quả của

bài toán NP_đầy đủ

I. Các khái niệm

1.1. Lớp bài toán P (polynomial time) 1.2. Lớp bài toán NP(Nondeterministic polynomial time) 1.3. Quan hệ giữa lớp P và lớp NP

II. Các bài toán NP_Complete

2.1. Phép dẫn với thời gian đa thức 2.2. Bài toán NP_Complete (NPC) 2.3. Một số bài toán NPC

I. Các khái niệm

1.1. Lớp bài toán P (polynomial time)

Lớp P là lớp bài toán quyết định giải được trong thời gian đa thức trên máy Turing tất định, hay lớp những bài toán dễ (có lời giải chấp nhận được).

1.2. Lớp bài toán NP

Là lớp bt quyết định giải được trong thời gian đa thức trên máy Turing không tất định

1.3. Quan hệ giữa lớp P và lớp NP

 Ta có thể thấy một cách trực quan là PNP. Nhưng chúng ta vẫn chưa biết P=NP hay không, nhưng hầu hết các nhà nghiên cứu tin rằng P≠NP là sự tồn tại của của lớp bt NPC

 Dù chúng ta chưa biết chắc chắn liệu P≠NP song việc chỉ ra được một bài toán là NPC chứng tỏ 1 sự thật là bt đó không thể giải được về phương diện tính toán với thuật toán chính xác, tốt hơn hết là lời giải theo thuật toán gần đúng.

 Việc xem xét quan hệ giữa P và NP dẫn đến chúng

ta đi đến nghiên cứu lớp NPC

II. Các bài toán NP_Comlete (NPC)

Phép dẫn với thời gian đa thức

Cho hai bài toán 1 và 2.

2.1 Phép dẫn với thời gian đa thức

Phép dẫn thời gian đa thức f biến đổi mỗi dữ kiện 1 thành dữ kiện 2 thỏa mãn :

1. f được thực hiện trong thời gian đa thức

2.

Ký hiệu: 1  2

Ví dụ phép dẫn thời gian đa thức

Ví dụ : 1 bài toán Chu trình Hamilton Instance: Đồ thị G vô hướng. Question: tồn tại hay không chu trình Hamilton

trong G?

The theory of NP-Completeness

7

Ví dụ phép dẫn thời gian đa thức

Ví dụ: 2 bài toán TST

Instance: n, các thành phố: C = {c1, c2,…cm}, khoảng cách giữa ci, cj là d(ci, cj)  Z+, B  Z+.

Question: Tồn tại hay

thỏa :

The theory of NP-Completeness

8

1(Hamiltonian)2(TSP) với B = n

3- 9

2.2. Bài toán NP_Comlete (NPC)

Chúng ta nói L là bài toán thuộc NPC nếu khẳng

 Định Nghĩa:

định sau là đúng

1) L  NP

2) L’ NP, có phép dẫn với thời gian đa

thức từ L’ về L

2.3. Bài toán NPC

* Bài toán SAT

 Bài toán SAT được phát biểu dưới dạng bt quyết định:

Instance: Cho trước n biến logic {x1, x2, …….. ,xn} và một tập hợp C tuyển của các tục biến (biến hoặc phủ định

của biến).

Question: Tồn tại hay không một phép gán giá trị cho

các biến sao cho mỗi cC có giá trị đúng?

Ví dụ C1 = {x1 v x2,, x1 v x2 v ¬x4, x5}.

C2 = {¬ x1, ¬ x2, x1 v x2v ¬ x4, x4}.

 Định lý: Bài toán SAT là NPC

3.1 MỘT SỐ ĐỊNH LÝ: NP_Comlete (NPC)

* Đ/L1:

Ta có 1  2 thì

- Nếu 2P thì 1P.

- Nếu 1NPC, 2NP thì 2NPC

3.2. Bài toán NP_Comlete (NPC)

* Đ/L2:

- Nếu có một bài toán NPC giải được trong

thời gian đa thức bởi máy TRTĐ thì P=NP.

- Nếu một bt bài toán NP nào đó không giải

được trong thời gian đa thức bởi máy TRTĐ

thì tất cả các bài toán NPC đều không giải

được trong thời gian đa thức bởi máy

TRTĐ.

 Chứng minh bài toán  NPC: chúng ta thực hiện 4

bước sau:

1) Chứng minh bt NP.

2) Lựa chọn bt ’ NPC.

3) Xây dựng hàm biến đổi f từ ’ sang 

4) Chứng minh rằng f là một biến đổi đa thức.

3.2. Một số bài toán NPC

3.3. Một số bài toán NPC

Sơ đồ chứng minh một số bài toán NPC

3.3. Một số bài toán NPC

* Bài toán 3SAT

 Bài toán 3SAT được phát biểu dưới dạng bt quyết định

như sau:

Instance: Cho trước n biến logic {x1, x2, …….. ,xn} là tập hợp C các tuyển gồm 3 tục biến,

Ví dụ: C = {x1 v x2v x3 , x1 v x2 v ¬x4}. Question: Tồn tại hay không một phép gán giá trị cho

các biến sao cho mọi cC đều đúng?

 Định lý: Bài toán 3SAT là NPC

3.3 Một số bài toán NPC

 Bài toán VC (Vertex Cover)

Instance: Cho đồ thị G=(V,E) và một số nguyên dương k≤|V|

Question: Tồn tại hay không một tập phủ đỉnh có kích cỡ ≤ k?

3.3 Một số bài toán NPC

 Bài toán Clique

Instance: Cho đồ thị G=(V,E) và một số nguyên dương k≤|V|

Question: Tồn tại hay không trong G một đồ thị con đầy đủ

với ít nhất k đỉnh?

3.3 Một số bài toán NPC

 Bài toán 3DM (3-dimensional Matching)

Instance: |W|=|X|=|Y|=q,

Question: Tồn tại M tập con q phần tử của W×X×Y sao cho không có 2 phần tử nào của M có tọa độ chung?

3.3 Một số bài toán NPC

 Bài toán Phân hoạch (Partition)

Instance: A = {a1 , a2, … , an }

Question: Tồn tại hay không phân hoạch A = A A sao cho

3.4 Bài toán NPH (NP-hard)

Định Nghĩa:

L là bài toán thuộc NPH nếuL’  NP có phép

dẫn với thời gian đa thức từ L’ về L.