Bài giảng Lý thuyết độ phức tạp: Lý thuyết NP - Đầy đủ

LÝ THUYẾT ĐỘ PHỨC TẠP

LÝ THUYẾT NP - ĐẦY ĐỦ

(THE THEORY OF NP - COMPLETENESS)

Giáo viên : PGS TSKH Vũ Đình Hoà

The theory of NP-Completeness

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

6. Phép dẫn thời gian đa thức và lớp NPC

5. Mối quan hệ giữa lớp P và lớp NP

The theory of NP-Completeness

7. Thuyết Cook

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.

The theory of NP-Completeness

 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∏ là các thể hiện đúng

1. BÀI TOÁN QUYẾT ĐỊNH

 Một bài toán quyết định phát biểu dưới dạng:

 Instance: …

 Question:…

 Instance: Cho 2 đồ thị G1 = (V1, E1) và G2 = (V2, E2)

 Question: đồ thị G1 có chứa một đồ thị con G1’ mà

 Ví dụ 1: bài toán sự đẳng cấu của đồ thị con

The theory of NP-Completeness

G1’ đẳng cấu với đồ thị G2 hay không?

1. BÀI TOÁN QUYẾT ĐỊNH

 Giải thích về đồ thị đẳng cấu:

The theory of NP-Completeness

G1’ đẳng cấu với G2 nếu như có |V1’| = |V2|, |E1’| = |E2| và ở đó tồn tại một song ánh f : V2  V1’ sao cho {u,v}  E2 khi và chỉ khi {f(u), f(v)}  E1’).

1. BÀI TOÁN QUYẾT ĐỊNH

 Ví dụ 2: Traveling Salesman

 Instance: Tập hữu hạn các thành phố: C = {c1, c2,…cm}, khoảng cách giữa hai thành phố ci, cj là d(ci, cj)  Z+, một số B  Z+.

 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

)

The theory of NP-Completeness

1. BÀI TOÁN QUYẾT ĐỊNH

 Một bài toán quyết định có thể được chuyển hoá từ một

bài toán tối ưu.

nhất trong số tất cả các đường đi nối 2 đỉnh đồ thị” ↔

 Ví dụ: Bài toán tối ưu là “tìm một đường đi có độ dài nhỏ

BTQĐ : thêm vào một tham số B và hỏi xem có đường đi

 Với điều kiện là hàm chi phí phải tương đối dễ đánh giá,

nào có độ dài L mà L ≤ B hay không?

bài toán quyết định có thể không khó khăn hơn bài toán

The theory of NP-Completeness

tối ưu tương ứng

1. BÀI TOÁN QUYẾT ĐỊNH

 Nếu tìm thấy một đường đi có độ dài nhỏ nhất cho bài

toán TST theo thời gian đa thức, cũng có thể giải quyết

bài toán quyết định được kết hợp theo thời gian đa thức.

 Lý thuyết NP đầy đủ giới hạn là chỉ chú ý tới các bài toán

quyết định nhưng cũng có thể mở rộng sự liên quan của

thuyết NP đầy đủ tới các bài toán tối ưu.

 Nguyên nhân của sự giới hạn này là các DPs có một bản

The theory of NP-Completeness

sao rất tự nhiên và nó được gọi là ngôn ngữ.

2. NGÔN NGỮ VÀ LƯỢC ĐỒ MÃ HÓA

 Với bất kì một tập hữu hạn các kí hiệu, chúng ta có

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ữ trên tập các chữ cái của .

The theory of NP-Completeness

 Định nghĩa ngôn ngữ:

2. NGÔN NGỮ VÀ LƯỢC ĐỒ MÃ HÓA

 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á.

The theory of NP-Completeness

 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

 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}

The theory of NP-Completeness

2. NGÔN NGỮ VÀ LƯỢC ĐỒ MÃ HÓA

 Một lược đồ mã hoá hợp lý phải đảm bảo 2 tính năng là :

 “Tính ngắn gọn” là các trường hợp của bài toán nên

được mô tả với sự khúc chiết một cách tự nhiên.

 “Khả năng giải mã” là đưa ra bất kì một thành phần cụ

thể nào của một trường hợp chung, thì lược đồ có khả

năng chỉ rõ một thuật toán có thời gian đa thức.

The theory of NP-Completeness

“tính ngắn gọn” và có “khả năng giải mã”.

2. NGÔN NGỮ VÀ LƯỢC ĐỒ MÃ HÓA

 Định nghĩa một lược đồ mã hoá chuẩn:

Lược đồ mã hoá chuẩn sẽ ánh xạ các thể hiện sang các

xâu có cấu trúc trên tâp chữ cái ψ = {0, 1, -, [,], (, ), …}.

The theory of NP-Completeness

 Định nghĩa xâu cấu trúc một cách đệ quy như sau:

2. NGÔN NGỮ VÀ LƯỢC ĐỒ MÃ HÓA

 Biểu diễn nhị phân của một số nguyên k (gồm các chữ

số 0 và 1), (đằng trước là dấu - nếu k là số âm) là một

xâu có cấu trúc biểu diễn số nguyên k.

 Nếu x là một xâu có cấu trúc biểu diễn số nguyên k, khi

đó [x] là một xâu có cấu trúc có thể được sử dụng như

một “tên” (name) .

 Nếu x1, x2, ..., xm là các xâu có cấu trúc biểu diễn các đối tượng X1,X2, …, Xm, khi đó (x1, …, xm) là một xâu có cấu trúc biểu diễn chuỗi (X1,…,Xm)

The theory of NP-Completeness

2. NGÔN NGỮ VÀ LƯỢC ĐỒ MÃ HÓA

 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 tử của nó như một chuỗi và xem như là xâu có cấu trúc tương ứng với chuỗi đó.

 Một đồ thị với tập đỉnh là V và tập cạnh là E được biểu

diễn bởi một xâu có cấu trúc (x, y), ở đó x là một xâu có

cấu trúc biểu diễn tập V và y là xâu có cấu trúc biểu diễn

tập E (các phần tử của E …)

The theory of NP-Completeness

2. NGÔN NGỮ VÀ LƯỢC ĐỒ MÃ HÓA

 Một hàm hữu hạn f : {U1, U2,…, Um} → W được biểu diễn bởi một xâu có cấu trúc {(x1, y1), …, (xm, ym)} ở đó xi là xâu có cấu trúc biểu diễn Ui và yi là xâu có cấu trúc biểu diễn f(Ui)  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ủ5a a và b là 1.

The theory of NP-Completeness

3. MÁY TURING TẤT ĐỊNH VÀ LỚP P

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

các ô vuông có đánh các nhãn là:… -3, -2, -1, 0, 1, 2, 3…

The theory of NP-Completeness

3. Một băng vô hạn nằm ngang với các ô vuông. Dưới

3. MÁY TURING TẤT ĐỊNH VÀ LỚP P

Bộ điều khiển trạng thái hữu hạn

Đầu đọc ghi

Băng vô hạn

3.1. Miêu tả máy Turing tất định

- 3

- 2

- 1

0

1

2

3

4

The theory of NP-Completeness

3. MÁY TURING TẤT ĐỊNH VÀ LỚP P

3.1. Miêu tả máy Turing tất định

 Một tập hợp T những kí hiệu, bao gồm một tập con   T

và một kí tự trắng b  T \ .

 Một tập hợp Q các trạng thái, bao gồm trạng thái bắt đầu

qo và hai trạng thái kết thúc là qY và qN.

 Một hàm chuyển trạng thái

ઠ: (Q - {qY, qN}) * T → Q * T * {-1, +1,0}

The theory of NP-Completeness

 Một chương trình cho một DTM gồm các thông tin:

2. MÁY TURING TẤT ĐỊNH VÀ LỚP P

3.1. Miêu tả máy Turing tất định

 Hàm chuyển trạng thái:  cho phép với mỗi trạng thái của

đị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

The theory of NP-Completeness

máy và một kí kiệu đọc được từ ô trống đối diện, ta xác

3. MÁY TURING TẤT ĐỊNH VÀ LỚP P

3.1. Miêu tả máy Turing tất định

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à q0, với đầu đọc ở ô chứa kí tự đầu tiên của xâu

2. Các bước tính toán: …

The theory of NP-Completeness

 Quá trình thực hiện của DTM

3. MÁY TURING TẤT ĐỊNH VÀ LỚP P

2.1. Miêu tả máy Turing tất định

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 

- Rời đầu đọc theo hướng của hàm dịch chuyển

- Đổi trạng thái hiện tại thành trạng thái của hàm dịch

chuyển.

The theory of NP-Completeness

 Quá trình thực hiện của DTM

3. MÁY TURING TẤT ĐỊNH VÀ LỚP P

3.1. Miêu tả máy Turing tất định

 Quá trình thực hiện của DTM

thái thừa nhận.

The theory of NP-Completeness

Xâu x được thừa nhận khi quá trình thực hiện đạt đến trạng

3. MÁY TURING TẤT ĐỊNH VÀ LỚP P

3.2. Ví dụ

 Cho các tập hợp sau:

T = {0, 1, b},  = {0, 1}

Q = {q0, q1, q2, q3, qY, qN}

 Cho xâu vào:

The theory of NP-Completeness

x = “10100”

3. MÁY TURING TẤT ĐỊNH VÀ LỚP P

 Hàm trạng thái cho trong bảng:

The theory of NP-Completeness

Quá trình thực hiện:

The theory of NP-Completeness

3. MÁY TURING TẤT ĐỊNH VÀ LỚP P

Bài tập

 Xây dựng máy Turing tất định xóa các từ

 Xây dựng máy Turing tất định xóa các từ và quay về

The theory of NP-Completeness

vị trí xuất đầu

4. LỚP P

 Cho M là một máy Turing tất định không có quá trình vô

hạn. Hàm phức tạp theo thời gian của M là hàm được định

 TM : Z+ → Z+

 TM (n) = max {m: có một x  *, với |x| = n, quá trình

thực hiện của M trên đầu vào x chiếm thời gian là m}.

The theory of NP-Completeness

nghĩa như sau:

4. LỚP P

TM(n) ≤ p(n).

 Thời gian tính trên máy Turing M được gọi là đa thức nếu như tồn tại một đa thức P sao cho tất cả n  Z+

 Định nghĩa: Lớp P là một lớp các bài toán quyết định

đa thức

giải được bởi một máy Turing tất định trong thời gian

 Một hàm tính với thời gian đa thức, nếu có một máy

The theory of NP-Completeness

Turring tính nó trong thời gian đa thức.

4. LỚP P

 Ví dụ:

Instance: n nguyên dương,

Question: n chia hết cho 2?

 . Ví dụ:

Instance: n nguyên dương,

Question: n là số nguyên tố?

The theory of NP-Completeness

4. LỚP P

 Ví dụ:

Instance: n nguyên dương và a1 < a2 < …, < an, k,

Question: Tồn tại i sao cho ai = k?

 . Ví dụ:

Instance: ,

Question: ?

The theory of NP-Completeness

2.3.Máy Turing không tất định& Lớp NP

 Máy Turing không tất định:

2.3.Máy Turing không tất định& Lớp NP

 Hoạt động tương tự như máy Turing tất định:  Giả sử máy làm việc với một Input x0* được đặt

vào các ô từ 1 đến x của băng.

 Giai đoạn phỏng đoán được thực hiện trên phần băng bên trái của dữ liệu vào (các ô được đánh số - 1,-2,...) trước khi quá trình tính toán bắt đầu, được thực hiện bởi cơ chế phỏng đoán và đầu phỏng đoán chỉ viết lên các ô đánh –1, -2..mỗi ô một kí hiệu nào đó thuộc * cho đến khi dừng lại ta có một từ u0* trên phía trái của phần băng chứa Input (gọi là từ được dự đoán) và giai đoạn phỏng đoán hoàn thành

2.3.Máy Turing không tất định& Lớp NP

+Yếu tố không tất định là ở chỗ trong giai đoạn

phỏng đoán việc viết kí tự nào vào các ô –1,-2,-3...

không xác định tức là có thể viết theo nhiều khả

năng khác nhau

+Có thể hình dung nếu coi mỗi quá trình tính toán có

môt input x trên máy Turing tất định M chỉ là một

“đường tính toán” (a computation path) thì mỗi quá

trình tính toán với mỗi input x trên NDTM là một

“cây tính toán” (a computation tree) với nhiều đường

tính toán được xử lý đồng thời

2.3.Máy Turing không tất định & Lớp NP



NDTM

DTM

q0

qY/qN

qN

qY

Sự khác biệt

2.3.Máy Turing không tất định& Lớp NP

 Ngôn ngữ đoán nhận bởi NDTM:

 Mỗi từ x được chấp nhận bởi máy Turing bất định M

nếu xuất phát với input x, máy Turing bất định M chuyển đến trạng thái qY.

 Kí hiệu là LM = {w0* M chấp nhận w} gọi là ngôn

ngữ đoán nhận được bởi máy NDTM

2.3.Máy Turing không tất định& Lớp NP

 Thời gian tính toán của NDTM: Được tính là thời gian tối thiểu của mọi quá trình tính toán chấp nhận x, nghĩa là tM(x)= min{t có quá trình tính toán chấp nhận Input x dừng lại sau t

bước}

 Độ phức tạp thời gian (thời gian tính) của máy NDTM, kí hiệu là TM(n) cũng chỉ xét trên các từ x LM được định nghĩa như sau:

 TM(n)= max{t x LM và x=n, tM(x)= t}