Luận văn Thạc sĩ Khoa học: Tìm hiểu độ phức tạp một số thuật toán

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN --------------------- Nguyễn Thế Quyền TÌM HIỂU ĐỘ PHỨC TẠP MỘT SỐ THUẬT TOÁN LUẬN VĂN THẠC SĨ KHOA HỌC

Hà Nội – Năm 2013

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN --------------------- Nguyễn Thế Quyền TÌM HIỂU ĐỘ PHỨC TẠP MỘT SỐ THUẬT TOÁN Chuyên ngành: Bảo đảm toán học cho máy tính và hệ thống tính toán Mã số: 60.46.35 LUẬN VĂN THẠC SĨ KHOA HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. Nguyễn Hữu Ngự

Hà Nội – Năm 2013

MỤC LỤC

MỞ ĐẦU ................................................................................................................... 3

CHƢƠNG 1. KIẾN THỨC CHUẨN BỊ .................................................................. 4

1.1. Máy Turing .......................................................................................................... 4

1.1.1. Máy Turing ............................................................................................... 4

1.1.2. Máy Turing tất định .................................................................................. 5

1.1.3. Máy Turing không tất định ....................................................................... 7

1.2. Khái niệm thuật toán ............................................................................................ 8

1.2.1. Khái niệm thuật toán ................................................................................. 8

1.2.2. Ví dụ về thuật toán.................................................................................... 9

1.2.3. Luận đề Church-Turing .......................................................................... 10

1.3. Độ phức tạp của thuật toán ................................................................................ 11

1.3.1. Độ phức tạp về thời gian ......................................................................... 11

1.3.2. Ví dụ cách tính độ phức tạp .................................................................... 12

CHƢƠNG 2. BÀI TOÁN VÀ ĐỘ PHỨC TẠP CỦA BÀI TOÁN ........................ 14

2.1. Bài toán là gì? .................................................................................................... 14

2.2. Một số bài toán quan trọng ................................................................................ 15

2.3. Độ phức tạp của bài toán ................................................................................... 20

CHƢƠNG 3. PHÂN LỚP CÁC BÀI TOÁN THEO ĐỘ PHỨC TẠP ................. 21

3.1. Lớp các bài toán P, NP và mối quan hệ giữa lớp P và lớp NP ............................ 21

3.1.1. Lớp P ...................................................................................................... 21

3.1.2. Lớp NP ................................................................................................... 21

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

3.2. Lớp các bài toán NPC. ....................................................................................... 21

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

3.2.2. Lớp các bài toán NPC ............................................................................. 22

3.2.3. Mối quan hệ giữa các lớp bài toán P, NP và NPC ................................... 22

3.2.4. Một số bài toán lớp NPC......................................................................... 23

1) Bài toán SAT. Định lý Cook .............................................................. 23

2) Bài toán 3SATIFIABILITY (3SAT) .................................................. 30

3) Bài toán 3-DIMENSIONAL MATCHING (3DM) ............................ 33

4) Bài toán VERTEX COVER (VC) ...................................................... 37

5) Bài toán CLIQUE .............................................................................. 39

6) Bài toán HAMILTON CIRCUIL (HC) .............................................. 39

7) Bài toán PARTITION ........................................................................ 39

8) Bài toán TRAVELING SALEMAN (TSP) ........................................ 39

KẾT LUẬN ............................................................................................................. 41

TÀI LIỆU THAM KHẢO ...................................................................................... 42

MỞ ĐẦU

Lý thuyết độ phức tạp là một lĩnh vực trung tâm của khoa học máy tính với các

kết quả liên quan chặt chẽ với sự phát triển và sử dụng các thuật toán. Nghiên cứu về lý

thuyết độ phức tạp sẽ giúp chúng ta hiểu biết sâu sắc và khám phá ra ranh giới của

những vấn để “có thể” tính toán với các nguồn tài nguyên hợp lý.

Trong bản luận văn này, trước hết chúng tôi tìm hiểu một số khái niệm quan

trọng của lý thuyết thuật toán như thuật toán và độ phức tạp của thuật toán. Trên cơ sở

đó, chúng tôi bước đầu tìm hiểu một số khái niệm quan trọng của lý thuyết độ phức tạp

như khái niệm bài toán, độ phức tạp của bài toán. Cuối cùng là chúng tôi tìm hiểu về

các lớp phức tạp của bài toán và mối quan hệ giữa các lớp phức tạp đó. Trong đó đặc

biệt quan tâm đến lớp phức tạp NP-đầy đủ.

Nội dung của bản luận văn bao gồm ba chương:

Chƣơng 1: Trình bày tóm tắt những kiến thức cơ bản và trọng tâm về lý thuyết

thuật toán như máy Turing đơn định, máy Turing không đơn định, thuật toán, độ phức

tạp thuật toán.

Chƣơng 2: Gồm có ba phần chính trình bày về khái niệm bài toán, danh sách

các bài toán quan trọng và khái niệm độ phức tạp của bài toán.

Chƣơng 3: Gồm có hai phần chính trình bày lớp các bài toán P, NP và lớp bài

toán NP-đầy đủ.

Để hoàn thành bản luận văn này, chúng tôi đã nhận được sự giúp đỡ tận tình của

thầy hướng dẫn – PGS.TS. Nguyễn Hữu Ngự và sự chỉ bảo góp ý của các thầy cô trong

Bộ môn Tin học, Khoa Toán – Cơ – Tin học và các bạn đồng nghiệp. Nhân đây, chúng

tôi cũng xin cảm ơn các thầy cô và các bạn đồng nghiệp đã giúp đỡ chúng tôi trong quá

trình làm luận văn.

CHƢƠNG 1. KIẾN THỨC CHUẨN BỊ

Trước khi nói về thuật toán, chúng ta hãy xem xét một mô hình tính toán thể

hiện khá tốt về các thuật toán.

1.1. Máy Turing (Turing machine)

1.1.1. Máy Turing

Gồm có:

1) Tập trạng thái trong hữu hạn

2) Băng vô hạn hai phía (về lý thuyết có thể kéo dài tuỳ ý cả hai phía)

3) Bảng tín hiệu vào, bảng tín hiệu trên băng và một đầu đọc-ghi

4) Bảng chuyển trạng thái

q



... ... ... ... B B B B a1 a2 ... ai ... an B B B

Một bước làm việc của máy gồm:

- Đầu đọc-ghi đọc tín hiệu trên băng

- Căn cứ vào trạng thái trong và tín hiệu đọc trên băng, đầu đọc-ghi sẽ ghi một

tín hiệu trên băng, dịch chuyển sang phải hoặc sang trái một ô và chuyển sang một

trạng thái trong nào đó.

Quy ước khi máy bắt đầu làm việc thì trạng thái là trạng thái đầu của máy, với

input hữu hạn trên băng, đầu đọc-ghi nằm ở ký tự bên trái nhất của input. Các kết quả

trung gian trong khi tính toán có thể lưu trên băng hoặc có thể tổ chức lưu vào trạng

thái trong (nhưng chú ý là số trạng thái trong của một máy phải hữu hạn).

1.1.2. Máy Turing tất định (DTM)

Có thể định nghĩa một cách hình thức một máy Turing tất định như sau: là một

bộ:

M =

trong đó:

- : là bảng tín hiệu trên băng (hữu hạn)

- : là bảng tín hiệu vào (hữu hạn),   

- Q: là tập trạng thái (trong) (hữu hạn)

- F: là hàm chuyển F: Q x   Q x  x {L,R}

- q0: trạng thái ban đầu (q0  Q)

- t1: trạng thái kết thúc (t1  Q)

- B: ký tự trắng, B  , B  

Ý nghĩa:

-  là các tín hiệu vào để ghi input

-  là các tín hiệu đọc và ghi trên băng

Hàm chuyển F(q, a) = (q', a', D) có thể cho bằng bảng như sau:

a ...

...

q (q', a', D)

... -

Ban đầu các tín hiệu trên băng là B, băng có thể kéo dài vô hạn ở cả hai chiều:

trái và phải.

Xâu a1a2...qai...ak được gọi là một hình trạng của máy, trong đó các ak , qQ,

có nghĩa là đầu đọc-ghi đang đọc ô thứ i, tín hiệu đang được đọc là ai.

Tại mỗi bước, máy ở trạng thái q, đầu đọc-ghi đọc tín hiệu ai tại ô trên băng,

hình trạng của máy có dạng a1a2...ai-1qai...ak. Theo hàm chuyển F(q, ai) = (q', c, D), máy

sẽ chuyển sang trạng thái q', ghi c lên băng (thay cho ai), đầu đọc-ghi chuyển sang phải

hay sang trái một ô tùy theo D là R hoặc L. Ta nói rằng máy M chuyển từ hình trạng:

H = a1a2...ai-1qai...ak

sang hình trạng:

H' = a1a2...q'ai-1cai+1...ak nếu D = L hoặc

H' = a1a2...ai-1cq'ai+1...ak nếu D = R

Ký hiệu H  H'.

Máy sẽ làm việc từng bước cho đến khi gặp hình trạng mà hàm chuyển F(s,a)

không xác định hoặc gặp trạng thái kết thúc t1.

Xâu x (input) trên bảng tín hiệu  (tức là x  *) gọi là được đoán nhận bởi

máy M nếu tồn tại dãy hình trạng H0, H1, ..., Hm sao cho:

H0  H1  ... Hm.

H0 là hình trạng ban đầu, input x được ghi trên băng, đầu đọc-ghi nhìn vào ký tự

đầu tiên của input, trạng thái của máy là q0, tức là:

H0 = q0a1a2...ai-1ai...an với x = a1a2...ai-1ai...an.

Hm có trạng thái là t1.

Tập N các xâu (ngôn ngữ trên ) thuộc * gọi là được đoán nhận bởi máy M

nếu N = {x | x*, x được đoán nhận bởi máy M}.

Các bài toán có thể có nhiều loại:

- Đoán nhận một tính chất của input

- Tính toán một giá trị

- ...

Chú ý: Hàm chuyển F có thể không xác định khắp nơi. Máy sẽ dừng khi gặp

trạng thái t1 kết thúc (cho trả lời "yes") hoặc dừng ở trạng thái khác t1 (cho trả lời "no")

hoặc gặp bộ (s, a) tại đó F(s, a) không xác định (cũng cho trả lời "no"). Tuy nhiên có

thể làm cho hàm chuyển F trở thành xác định khắp nơi nếu thêm một trạng thái kết

thúc phủ định qp, và với mọi bộ (s, a) tại đó F(s, a) không xác định cho máy chuyển

sang trạng thái qp

F(s, a) = (qp, , ).

Nếu không có gì khác thì ngầm định bảng tín hiệu vào là  = {0,1}, và chủ yếu

ta chỉ xét ví dụ trên các bài toán đoán nhận.

Ký hiệu q0 là trạng thái đầu, t1 là trạng thái kết thúc khẳng định.

Ví dụ: Máy Turing đoán nhận ngôn ngữ {x | x có độ dài chẵn}

0 1 B

q0 (q1, 0, R) (q1, 0, R) (t1, B, ' ')

- q1 (q0, 0, R) (q0, 0, R)

Với input 010110 ta có dãy hình trạng:

(q0)010110  0(q1)10110  01(q0)0110  010(q1)110 

0101(q0)10  01011(q1)0  010110(q0)  010110(t1)

trạng thái cuối cùng là trạng thái kết thúc đoán nhận t1.

1.1.3. Máy Turing không tất định (NTDM)

Định nghĩa như máy Turing tất định, trong đó hàm chuyển F là hàm đa trị nghĩa

là F: Q x   2Q x  x {L,R}.

Tại mỗi bước, có thể chuyển sang bước sau bằng một trong các khả năng tùy

theo hàm chuyển F. Nếu có một nhánh đoán nhận input x thì xem như máy đoán nhận

input đó.

Giả sử F(s, a) = {(si1, ai1, Di1), (si2, ai2, Di2), ..., (sim, aim, Dim)} là một tập (có thể

rỗng). Với hình trạng H với trạng thái s và tín hiệu a được đọc máy có thể chuyển đến

một trong các hình trạng:

H  Hi1, H  Hi2, ..., H  Him

trong đó Hik có trạng thái sik và tín hiệu được ghi là aik.

Có thể biểu diễn các bước làm việc của máy bằng hàng đợi hoặc bằng cây.

Ví dụ:

0 B 1

(q0,1,R) q0 (q1,1,R)

(t1,' ',' ') q1 (q2,0,L)

q2 (q0,1,R)

Với w = 010

(q0)010 1(q0)10 1(q1)10 (q2)100 1(q0)00 11(q0)0 11(q1)0

111(q0) 111(q1)B (t1)

1.2. Khái niệm thuật toán (algorithm)

Bài toán xử lý thông tin:

Công cụ Input   Output

Với dữ liệu vào (input) công cụ sẽ tính toán và cho kết quả theo yêu cầu của bài

toán. Nói chung ta phân biệt một số loại bài toán:

- Những bài toán đoán nhận một tính chất (xét số nguyên n có phải nguyên tố

hay không,...)

- Những bài toán tính giá trị một hàm

- Những bài toán tìm một lời giải (tìm đường đi trên đồ thị, tìm chu trình

Hamilton, ...).

Để giải quyết bài toán cần thuật toán. Thuật toán là công cụ xử lý thông tin.

1.2.1. Khái niệm

Một cách không hình thức thì thuật toán là việc mô tả một cách chính xác quá

trình thực hiện trên các đối tượng để nhằm đạt được một kết quả nào đó theo một yêu

cầu cho trước.

Cần chú ý đặc trưng hữu hạn trong thuật toán:

- Đối tượng hữu hạn, thao tác hữu hạn

- Cho kết quả qua một số hữu hạn bước.

Ta phân biệt hai loại thuật toán: tất định và không tất định. Đối với thuật toán tất

định tại mỗi thời điểm chỉ có không quá một bước tiếp theo. Đối với thuật toán không

tất định tại mỗi thời điểm có thể có một số khả năng để lựa chọn bước tiếp theo.

Thông thường để mô tả thuật toán (tức là chỉ dẫn ở mỗi bước cần thực hiện

những công việc gì) ta dùng một văn bản hướng dẫn các bước, một sơ đồ khối, một

ngôn ngữ lập trình nào đó, hoặc một ngôn ngữ tựa Pascal, ...

1.2.2. Ví dụ về thuật toán

Ví dụ: Thuật toán sắp dãy số tăng bằng đổi chỗ trực tiếp

Input: n và dãy số n phần tử a1, a2, ..., an .

Output: Dãy số a1, a2, ..., an được sắp xếp tăng.

Mô tả cụ thể các bước:

1. i = 1

2. k = i + 1

3. Nếu ai > ak thì hoán vị ai với ak

4. k = k + 1

5. Nếu k <= n thì trở lại 3

6. i = i + 1

7. Nếu i < n thì trở lại 2.

Ngôn ngữ giả Pascal:

For i = 1 to n - 1 do

For k = i + 1 to n do

if ai > ak then hoán vị giá trị ai với ak cho nhau.

Sơ đồ khối:

Nhập n, dãy số a1, ..., an

i = 1

k = i+1

Đ hoán vị ai với ak ai>ak

S k = k+1

Đ

k

S

i = i+1

Đ

i

Đưa ra dãy số a1, ..., an

1.2.3. Luận đề Church-Turing

Một vấn đề được đặt ra là: liệu có bài toán nào giải được bằng một cách nào đó

(được biết cho đến nay) mà không thực hiện được trên máy Turing (hoặc trên các mô

hình thuật toán tương đương)?

Luận đề Church-Turing phát biểu như sau: những bài toán có thể giải được trên

một mô hình tính toán nào đó được biết cho đến nay đều có thể tính được trên máy

Turing.

1.3. Độ phức tạp của thuật toán

Để đánh giá hiệu quả của một thuật toán, ta có thể đánh giá độ phức tạp của

thuật toán về mặt thời gian, tức là thời gian máy tính làm việc và về không gian, tức là

dung lượng bộ nhớ của máy tính cần thiết để thực hiện thuật toán. Trong luận văn này,

khi nói đến độ phức tạp của thuật toán ta luôn hiểu là độ phức tạp về thời gian.

1.3.1. Độ phức tạp về thời gian

Thời gian làm việc của máy tính khi chạy một thuật toán nào đó không chỉ phụ

thuộc vào thuật toán, mà còn phụ thuộc vào máy tính được sử dụng. Vì thế, để có một

tiêu chuẩn chung, ta sẽ đo độ phức tạp của một thuật toán bằng số các phép tính phải

thực hiện. Khi thực hiện cùng một thuật toán, số các phép tính phải thực hiện còn phụ

thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào. Vì thế, độ phức tạp của thuật toán

sẽ là một hàm số phụ thuộc độ lớn của đầu vào. Trong những ứng dụng thực tiễn,

chúng ta không cần biết chính xác hàm này, mà chỉ cần biết “cỡ” của chúng, tức là cần

có một ước lượng đủ tốt của chúng.

Giả sử A là một thuật toán. Ký hiệu T(X) là thời gian tính toán với đầu vào X.

Độ phức tạp của thuật tính trong trường hợp xấu nhất:

T(n) = max {T(X), X có độ dài bằng n}

Nếu A là thuật toán không tất định, thì T(n) là độ dài dài nhất trong các nhánh

làm việc với đầu vào X.

Trên thực tế còn xét đến độ phức tạp trong trường hợp trung bình:

T(X), X có độ dài bằng n

Ttb(n) = số các dữ liệu có thể với độ dài n

Để ước lượng độ phức tạp của thuật toán, ta dùng khái niệm bậc O-lớn và bậc

(bậc Theta).

Giả sử f(n) và g(n) là hai hàm xác định trên tập hợp các số nguyên dương. Ta

nói f(n) có bậc O-lớn của g(n), và viết f(n) = O(g(n)) hoặc f = O(g), nếu tồn tại n0 và

hằng số dương C sao cho với mọi n  n0 luôn có f(n)  C.g(n).

Nếu tồn tại n0 và các hằng số dương C1 và C2 sao cho với mọi n  n0 luôn có

C1g(n)  f(n)  C2g(n), thì ta ký hiệu f(n) = (g(n)).

Ký hiệu O nói rằng hàm f(n) bị chặn trên bởi g(n) (sai khác một hằng số dương),

còn ký hiệu  nói rằng hàm f(n) tương đương với g(n) (sai khác các hằng số dương).

Nếu thuật toán A có T(n) = O(g(n)) thì g(n) mới chỉ là chặn trên của T(n), còn

nếu T(n) =(g(n)) thì g(n) mới là tượng trưng chính xác cho độ phức tạp của thuật

toán. Tuy nhiên việc tính O dễ hơn việc tính . Nếu T(n) = O(g(n)) (hoặc tốt hơn là

(g(n))) trong đó g(n) là một đa thức theo n thì ta nói rằng thuật toán làm việc với thời

gian đa thức, gọi tắt là thuật toán đa thức. Thuật toán đa thức thường được xem là tốt.

1.3.2. Ví dụ cách tính độ phức tạp

Ví dụ 1: Thuật toán tìm kiếm nhị phân

Input: dãy số tăng a1, ..., an; số x.

Output: trả lời x có thuộc dãy hay không

Dùng thuật toán đệ quy DQ(a, b) (tìm trên đoạn con [d, c])

1. Nếu d = c và a(c) = x return "yes"

2. c = (a + b)/2

3. Nếu a(c) = x return "yes"

4. Nếu x < a(c) thì gọi DQ(a, c-1) else gọi DQ(c+1, b)

Để tìm nghiệm, gọi DQ(1, n)

Đánh giá độ phức tạp: T(2*k) = T(k) + 2.

T(1) = 1

T(2) = T(1) + 2

... T(2k) = T(2k-1) + 2 Lấy 2k xấp xỉ n, T(n) = T(2k) (cộng từng vế và khử)

= 2*k – 1 = 2*log2n - 1 = O(logn).

Ví dụ 2: (tính độ phức tạp trung bình)

Máy Turing đoán nhận ngôn ngữ {X | X  {0,1}* có ít nhất một chữ số 1} Số dữ liệu có thể với độ dài n là s = 2n

Số các X không có chữ số 1 (không được đoán nhận) là 1 (duy nhất "00...0"),

thời gian T(X) = n, tỷ lệ không đoán nhận là T0(n) = n/s.

Với i  n thì số các X (được đoán nhận) có X(i) = '1', và X(k) = '0' với k < i, là

2n-i, với thời gian T(X) = i.

Tổng thời gian tính với các X này là: h = 1*2n-1 + 2*2n-2 + ... + n*2n-n

Tỷ lệ đoán nhận là T1(n) = h/s = t

t = 1*2-1 + 2*2-2 + ... + (n-1)*2-(n-1) + n*2-n

Đặt c = 1/2 (khi đó T0(n) = n/s = n*cn) t = c + 2*c2 + ... + (n-1)*cn-1 + n*cn

c*t = c2 + 2*c3 + ... + (n-1)*cn + n*cn+1 t - c*t = c + c2 + ... + cn + n*cn+1 = c*[(1- cn)/(1- c) - n*cn]

T1(n) = t = c*[(1- cn)/(1- c) - n*cn ]/(1-c) (vì c/(1-c) = 1) Vậy Ttb(n) = T1(n) + T0(n) = (1- cn)/(1- c) - n*cn + n*cn = 2 - 1/2n-1.

Trong khi đó độ phức tạp T(n) = n.

CHƢƠNG 2. BÀI TOÁN VÀ ĐỘ PHỨC TẠP CỦA BÀI TOÁN

2.1. Bài toán là gì?

Trong giới hạn của chúng ta, sẽ chỉ xem xét các bài toán là một vấn đề phù hợp

với tính toán của máy tính và một tập hợp các kết quả chính xác. Vấn đề về tìm kiếm

một bản án thích đáng dành cho bị cáo không phải là bài toán vì nó phụ thuộc vào tư

pháp và do đó nó không thích hợp cho việc xử lý của máy tính. Mặt khác, vấn đề về

việc dịch một văn bản tiếng Đức sang một ngôn ngữ khác thì phù hợp với việc xử lý

của phép tính, nhưng trong trường hợp này không rõ các kết quả có chính xác hay

không. Vì vậy vấn đề dịch thuật cũng không phải là một bài toán. Một ví dụ rõ ràng về

một bài toán là việc tính toán con đường ngắn nhất từ đỉnh s đến đỉnh t trong một đồ thị

mà trong đó mỗi cạnh được gắn với một chi phí dương (chúng ta có thể diễn giải như

khoảng cách hay thời gian di chuyển).

Một bài toán được xác định bởi:

 Một mô tả tập hợp đầu vào được phép, mỗi một đầu vào có thể được thể hiện

như là một chuỗi hữu hạn trên một bảng chữ cái hữu hạn (tập hợp ký hiệu của

máy tính)

 Một phát biểu về các tính chất mà câu trả lời (hoặc giải pháp) cần phải thoả

mãn.

Thông thường bài toán được mô tả như trong ví dụ sau:

Đầu vào: Một số nguyên dương n

Câu hỏi: n có nguyên tố không?

Trong mỗi trường hợp, khi chúng ta tìm kiếm một trong nhiều câu trả lời chính

xác tiềm năng, chúng ta coi bài toán như là một bài toán tìm kiếm. Nếu chúng ta tìm

kiếm một giải pháp tối ưu về mặt nào đó, chúng ta coi bài toán đó như là một bài toán

tối ưu (ví dụ như trường hợp tìm kiếm một đường đi ngắn nhất). Thông thường, tính

toán giá trị của một giải pháp tối ưu là đủ (ví dụ, độ dài của một con đường ngắn nhất).

Những biến thể này được gọi là các bài toán đánh giá. Bài toán đánh giá luôn luôn có

giải pháp duy nhất. Trong trường hợp đặc biệt, khi câu trả lời có thể chỉ là 0 (không) và

1 (có) và chúng ta phải quyết định khả năng nào trong hai khả năng này là chính xác,

thì lúc đó chúng ta nói về một bài toán quyết định. Các bài toán quyết định phát sinh tự

nhiên trong nhiều tình huống: Từ một cấu hình cho trước của một bàn cờ, liệu quân cờ

màu trắng có một chiến lược giành chiến thắng không? Có phải con số đưa ra là một số

nguyên tố không? Có thể thoả mãn các điều kiện đã quy định không?

Các bài toán bao gồm tất cả các vấn đề có thể xử lý được bởi máy tính và chúng

ta có thể phân biệt một cách rõ ràng giữa các giải pháp chính xác và không

chính xác. Trong số này có các bài toán tối ưu và các bài toán với các giải pháp

duy nhất như các bài toán đánh giá và các bài toán quyết định. Các định dạng

đầu vào khác nhau cho cùng một “bài toán” sẽ đưa đến các bài toán khác nhau,

nhưng thông thường những bài toán này về mặt thuật toán rất giống nhau.

2.2. Một số bài toán quan trọng

1) Các bài toán về ngƣời bán hàng

Bài toán người bán hàng (TSP): là bài toán tìm kiếm một chu trình ngắn nhất

qua n thành phố, mỗi thành phố đúng một lần và quay trở lại điểm xuất phát của nó.

Các thành phố được ký hiệu bằng các nhãn là 1, ..., n và các khoảng cách giữa các

 {∞}, và giá trị ∞ thành phố là di,j (1 ≤ i, j ≤ n). Các khoảng cách được chọn từ tập

có nghĩa là không có sự kết nối trực tiếp giữa hai thành phố cụ thể. Mỗi chu trình là

một phép hoán vị π của {1, …, n}, do đó các thành phố đã đến được sắp xếp theo thứ tự

là π(1), π(2), …, π(n), π(1). Giá trị của một chu trình π được tính bởi:

dπ(1), π(2) + dπ(2), π(3) + … + dπ(n-1), π(n) + dπ(n), π(1)

và một chu trình có giá trị cực tiểu cần được tính toán. Có nhiều biến thể đối với bài

toán này. TSP (hoặc TSPOPT) là ký hiệu cho bài toán tối ưu nói chung. TSPEVAL và

TSPDEC ký hiệu cho các bài toán ước lượng và bài toán quyết định có liên quan. Đối

với bài toán quyết định, đầu vào bao gồm một giới hạn D và phải xác định có hay

không một chu trình có giá trị không vượt quá D. Chúng ta cũng sẽ xem xét các biến

thể bị giới hạn sau đây:

 TSPSYM: các khoảng cách là đối xứng (di,j = dj,i)  TSP∆: các khoảng cách thoả mãn bất đẳng thức tam giác, có nghĩa là di,j≤di,k+dk,j  TSPd-Euclid: các thành phố là các điểm trong không gian Euclide d chiều Rd và

khoảng cách tương ứng với khoảng cách Euclide (chuẩn L2)

 TSPN: các khoảng cách thuộc {1, …, N} (N là một số tự nhiên xác định)

 DHC (Chu trình Hamilton định hướng): khoảng cách thuộc {1, ∞}, và các định

dạng đầu vào thông thường là một đồ thị định hướng chỉ chứa những cạnh có

giá trị bằng 1.

 HC = DHCSYM: biến thể đối xứng của DHC, mà định dạng đầu vào thông

thường là một đồ thị vô hướng chỉ chứa những cạnh có giá trị bằng 1.

2) Các bài toán về xếp ba lô

Làm thế nào để một hành khách thu xếp hành lý của mình trong giới hạn W

từ n đồ vật muốn mang theo với giả thiết rằng đồ vật thứ i (i = ) có trọng lượng

được gọi là bài toán xếp ba lô (KNAPSACK). Hành khách wi và có giá trị ui 

không được phép mang các đồ vật có tổng trọng lượng vượt quá W. Do hạn chế này,

mục tiêu là tối đa hoá tổng giá trị của tất cả các đồ vật được chọn. Ở đây, cũng có các

biến thể mà trong đó các giá trị ui và/hoặc các trọng lượng wi đều bị chặn. Trong

trường hợp tổng quát, các đồ vật có những giá trị khác nhau trên mỗi đơn vị trọng

lượng.

KNAPSACK* biểu thị trường hợp đặc biệt với ui = wi cho tất cả các đồ vật. Mục

tiêu chỉ là để đạt tới càng gần càng tốt giới hạn trọng lượng mà không bị vượt quá mức

quy định. Hơn nữa, nếu W = (w1 + w2 + … + wn)/2, và chúng ta xem xét bài toán quyết

định là liệu chúng ta có thể đạt được trọng lượng tối đa cho phép hay không, thì bài

toán sẽ tương đương với câu hỏi liệu tất cả các đồ vật có thể được chia thành hai nhóm

có tổng trọng lượng giống nhau không. Trường hợp đặc biệt này được gọi là bài toán

phân hoạch (PARTITION).

3) Các bài toán về phân hoạch

Bài toán phân hoạch (PARTITION) cũng là một trường hợp đặc biệt của bài

toán đóng thùng (BINPACKING), trong đó các thùng có kích thước b có sẵn, chúng ta

phải đóng thùng n đồ vật với các kích cỡ u1, u2, ..., un vào càng ít thùng càng tốt.

Nhưng chúng ta cũng có thể xem BINPACKING như là một trường hợp rất đặc biệt

của bài toán lập lịch. Lớp của các bài toán lập lịch là gần như không thể đạt được về

mặt tổng quát. Trong mỗi trường hợp, các nhiệm vụ phải được phân chia giữa con

người hoặc máy móc với những hạn chế ở các mặt khác nhau. Không phải tất cả mọi

người đều thích hợp cho mọi nhiệm vụ, những người khác nhau có thể cần những

khoảng thời gian khác nhau để hoàn thành cùng một nhiệm vụ, những nhiệm vụ nhất

định có thể cần được hoàn thành theo một trình tự cụ thể, có thể xác định những thời

điểm bắt đầu sớm nhất hoặc những thời điểm hoàn thành chậm nhất (các thời hạn

chót), và có thể sử dụng các điều kiện tối ưu khác nhau.

4) Các bài toán giám sát (hoặc phủ)

Một bài toán giám sát điển hình là bài toán triển lãm nghệ thuật. Yêu cầu đưa ra

là giám sát tất cả các bức tường của một phòng triển lãm với càng ít máy quay càng tốt.

Chúng ta sẽ hạn chế trong các bài toán giám sát trên các đồ thị vô hướng, trong trường

hợp đó chúng thường được gọi là các bài toán phủ. Trong bài toán phủ đỉnh

(VERTEXCOVER), mỗi đỉnh sẽ theo dõi tất cả các cạnh liên quan tới nó, và tất cả các

cạnh được theo dõi với càng ít đỉnh càng tốt. Trong bài toán phủ cạnh

(EDGECOVER), các vai trò đảo ngược lại: mỗi cạnh theo dõi hai đỉnh liên quan đến

nó, các đỉnh sẽ được giám sát với càng ít cạnh càng tốt.

5) Các bài toán clique

Các đỉnh của đồ thị có thể được sử dụng để biểu diễn con người, các cạnh sẽ

biểu diễn mối quan hệ giữa mọi người. Một clique được định nghĩa là một nhóm trong

đó mỗi người thích những người khác trong nhóm. Trong bài toán phủ clique

(CLIQUECOVER), các đỉnh của một đồ thị phải được phân chia thành càng ít tập hợp

càng tốt, theo cách như vậy mỗi tập hợp tạo thành một clique. Trong bài toán clique

(ký hiệu là CLIQUE), một clique lớn nhất có thể sẽ được tính toán. Một anti-clique

(“không ai thích ai cả”, giữa hai đỉnh bất kỳ không có một cạnh nào) được gọi là một

tập hợp độc lập, và bài toán tính toán một tập hợp độc lập lớn nhất được gọi là

INDEPENTSET.

6) Các bài toán xây dựng nhóm

Xây dựng nhóm có nghĩa là phân chia những người với khả năng khác nhau vào

các nhóm hợp tác, trong đó các thành viên của mỗi nhóm phải làm việc cùng nhau. Đối

với bài toán k-DM (đối sánh k chiều, nghĩa là xây dựng các nhóm có kích thước k),

chúng ta có sẵn k nhóm người (mỗi nhóm đại diện cho một trong k khả năng), và danh

sách các nhóm k thành viên tiềm năng, trong đó mỗi người đến từ các nhóm khả năng.

Mục đích là để hình thành nên càng nhiều nhóm càng tốt với hạn chế là mỗi người chỉ

có thể được tham gia vào một nhóm. 2-DM cũng được biết đến như là bài toán hôn

nhân: hai “khả năng” được hiểu như là hai giới tính, một nhóm có tiềm năng được xem

như là một cuộc “hôn nhân bền vững”, và mục tiêu là tối đa hoá số lượng các cuộc hôn

nhân bền vững.

7) Các bài toán luồng tối ƣu trong các mạng

Trong bài toán luồng qua mạng (NETWORKFLOW), người ta tìm kiếm các

luồng tối đa trong các mạng. Chúng ta chỉ quan tâm đến bài toán cơ bản mà trong đó

chúng ta tìm kiếm để tối đa hoá luồng từ s đến t trong một đồ thị có hướng. Luồng f(e)

chạy theo một cạnh e phải là số nguyên không âm bị chặn trên bởi khả năng c(e) của

cạnh đó. Luồng tổng đạt đến một đỉnh v  {s, t}, nghĩa là tổng số f(e) với e = (., v) phải

bằng luồng tổng rời khỏi v, tức là tổng số f(e) với e = {v, .}. Đỉnh nguồn s không có bất

kỳ cạnh nào đi vào và đỉnh đích t không có bất kỳ cạnh nào đi qua.

8) Các bài toán vô địch trong các giải đấu thể thao

Bài toán vô địch (CHAMPIONSHIP) cơ bản là một bài toán quyết định. Một cổ

động viên tự hỏi tại một thời điểm cụ thể trong mùa giải liệu có thể (ít nhất là về mặt lý

thuyết) đội bóng yêu thích của mình sẽ vô địch trong giải đấu được không. Cho biết

xếp hạng hiện tại của mỗi đội chơi và có một danh sách các trận đấu còn được chơi.

Đội được chọn có thể trở thành nhà vô địch nếu có kết quả tiềm năng của các các trận

đấu còn lại sao cho đến cuối giải không đội nào khác có nhiều điểm hơn (nếu cần thiết,

đội chơi có thể cũng cần phải có hiệu số bàn thắng thua tốt nhất). Ngoài ra, một trong

những quy tắc sau đây phải chỉ rõ bao nhiêu điểm đạt được trong mỗi trận đấu:

 Quy tắc a-điểm: Sau mỗi trận đấu, a điểm được tính (a  ), và mỗi phân chia

a thành b điểm cho đội chơi 1 và a – b điểm dành cho đội chơi 2 với 0 ≤ b ≤ a và

b  là có thể.

 Quy tắc (0, a, b)-điểm: các khả năng chỉ là b : 0 (đội nhà chiến thắng), a : a

(hoà) và 0 : b.

Trong thực tế, ở các môn thể thao khác nhau, các quy tắc tính điểm khác nhau

được sử dụng gồm: quy tắc 1-điểm được sử dụng trong môn thể thao không cho phép

có kết quả hoà (bóng rổ, bóng chuyền, …). Quy tắc 2-điểm (tương đương với quy tắc

(0, 1, 2)-điểm) là quy tắc cổ điển trong thể thao chấp nhận tỷ số hoà (bóng ném đồng

đội, ...). Quy tắc 3-điểm được sử dụng trong giải khúc côn cầu trên băng ở Đức (DEL).

Quy tắc (0, 1, 3)-điểm hiện tại đang được sử dụng trong bóng đá.

9) Các bài toán xác minh

Đối với lớp của các bài toán xác minh, chúng ta đề cập tới lĩnh vực phần cứng.

Bài toán cơ bản là liệu đặc tả S và nhận dạng R của một chíp có mô tả cùng một hàm

số Boolean không. Tức là, chúng ta có các mô tả S và R của các hàm Boolean f và g và

tự hỏi liệu f(a) = g(a) với tất cả các yếu tố đầu vào a không. Vì chúng ta thực hiện các thao tác bit xác minh, có thể giả sử rằng f, g: {0, 1}n → {0, 1}. Tính chất f ≠ g tương

đương với tồn tại một a mà (f  g)(a) = 1 ( = XOR). Vì vậy, chúng ta đặt ra câu hỏi

liệu h = f  g có thể thoả được không, tức là liệu h có thể cho ra giá trị 1 không. Bài

toán quyết định này được gọi là bài toán thoả được.

 SATCIR: đầu vào được biểu diễn như một mạch logic.

 SAT = CNF-SAT = SATCNF: đầu vào được biểu diễn như một hội của các mệnh

đề (là tuyển của các literal), nghĩa là ở dạng chuẩn tắc hội.

 DNF-SAT = SATDNF: đầu vào được biểu diễn như là một tuyển của các đơn

thức (là hội của các literal), nghĩa là ở dạng chuẩn tắc tuyển.

10) Các bài toán lý thuyết số

Mật mã học hiện đại có kết nối chặt chẽ với các bài toán lý thuyết số, trong đó

các số rất lớn được sử dụng. Đã từng được học trong trường, hầu hết chúng ta học thuật

toán về cộng các phân số đòi hỏi chúng ta phải tính toán mẫu số chung và để làm được

điều đó, chúng ta sẽ phân chia các mẫu số thành các thừa số nguyên tố. Đây là bài toán

tạo thừa số nguyên tố (FACT).

2.3. Độ phức tạp của bài toán

Đối với một bài toán có rất nhiều thuật toán để giải. Ta ký hiệu:

TA(n) = max {T(X), X đầu vào có độ dài n}

là độ phức tạp của thuật toán A.

Độ phức tạp của bài toán B được định nghĩa như sau:

TB(n) = inf {TA(n), A là thuật toán giải bải toán B}

Rất khó tính được TB(n), mà thường chỉ biết được cận dưới và cận trên của

TB(n). Nếu ta xây dựng được một thuật toán A giải bài toán B thì TB(n)  TA(n), có

nghĩa là độ phức tạp của bài toán B nhỏ hơn hoặc bằng độ phức tạp của thuật toán A

(một cận trên). Để chứng tỏ TB(n)  f(n) (một cận dưới) thì ta phải chứng minh rằng

bất kỳ thuật toán A nào giải bài toán B cũng đều có độ phức tạp lớn hơn hoặc bằng

f(n).

CHƢƠNG 3. PHÂN LỚP CÁC BÀI TOÁN THEO ĐỘ PHỨC TẠP

3.1. Lớp các bài toán P, NP và mối quan hệ giữa lớp P và lớp NP

3.1.1. Lớp P

Định nghĩa:

Lớp P là lớp những bài toán giải được bằng máy tính Turing tất định trong thời

gian đa thức.

Ví dụ: Bài toán tìm ước chung lớn nhất của hai số nguyên dương, bài toán kiểm

nghiệm tính nguyên tố...

3.1.2. Lớp NP

Định nghĩa:

Lớp NP là lớp các bài toán có thể giải được bằng máy Turing không tất định

trong thời gian đa thức.

Ví dụ: Bài toán người bán hàng, bài toán chu trình Hamilton, ...

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

- Đến nay vẫn chỉ có thể khẳng định là P  NP mà chưa kết luận được P  NP

hay không.

NP P

Hình 1. Mối quan hệ giữa lớp P và NP.

3.2. Lớp các bài toán NP-đầy đủ (NPC)

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

Định nghĩa:

Cho 1 và 2 là hai bài toán quyết định

i(y) là lớp các đầu vào ứng với Yes (với i  {1, 2})

i(n) là lớp các đầu vào ứng với No

Một cách biến đổi f biến mỗi đầu vào của 1 thành đầu vào của 2 được gọi là

phép dẫn thời gian đa thức (ký hiệu là ) nếu nó thoả mãn:

- Biến đổi f thực hiện được trong thời gian đa thức bởi máy tính Turing tất định.

- Mỗi dữ kiện thuộc 1(y) thành dữ kiện thuộc 2(y)

- Mỗi dữ kiện thuộc 1(n) thành dữ kiện thuộc 2(n)

3.2.2. Lớp các bài toán NPC (NP-Complete, NP-đầy đủ)

Định nghĩa:

Một bài toán thuộc lớp NP mà mọi bài toán thuộc lớp NP khác đều dẫn được về

nó với thời gian đa thức được gọi là bài toán NPC.

Một bài toán  là NPC nếu nó thoả mãn:

-   NP

- Với  ’  NP thì ’ dẫn được về  với thời gian đa thức.

Như vậy để chứng minh một bài toán là NPC ta cần chứng minh hai điều:

- Bài toán đó phải thuộc lớp NP

- Mọi bài toán thuộc lớp NP đều dẫn được về bài toán đó với thời gian đa thức.

3.2.3. Mối quan hệ giữa các lớp bài toán P, NP và NPC

Do bài toán P = NP chưa được giải quyết, nếu có thể quy một bài toán NP-đầy

đủ Π2 về bài toán Π1 thì chưa có thuật toán thời gian đa thức nào cho Π1. Bởi vì nếu có

thuật toán thời gian đa thức cho Π1 thì cũng có thuật toán thời gian đa thức cho Π2.

Tương tự như vậy, do mọi bài toán trong NP đều có thể quy về các bài toán NP-đầy đủ,

nếu có thể giải được một bài toán NP-đầy đủ trong thời gian đa thức thì P = NP.

NP NPC

P

Hình 2. Mối quan hệ giữa lớp P, NP và NPC.

3.2.4. Một số bài toán lớp NPC

Cho U = {u1, u2, ..., un} là một tập các biến Boolean.

Một phép gán (truth assignment) cho U là một hàm t: U  {T,F}. Nếu t(u) = T

chúng ta nói rằng u là true theo t; nếu t(u) = F chúng ta nói rằng u là false theo t. Nếu u

là một biến trong U, thì u và là các literal trên U.

Một mệnh đề trên U là một tập các literal trên U, ví dụ {u1,, ,u8). Một mệnh đề

biểu diễn dạng tuyển của các literal đó, và “thỏa được” bởi một phép gán nếu và chỉ

nếu có ít nhất một literal là True theo phép gán đó.

Ví dụ: Mệnh đề ở trên sẽ thỏa được theo t, ngoại trừ trường hợp t(u1)=F,

t(u3)=T, t(u8)=F.

Tập các mệnh đề C trên U là “thỏa được” nếu và chỉ nếu tồn tại một phép gán

nào đó cho U mà “thỏa được” với tất cả mệnh đề trong C. Một phép gán như vậy được

gọi là một phép gán thỏa được cho C.

1) Bài toán SAT. Định lý Cook

Bài toán SAT được mô tả như sau:

- Đầu vào: Cho một tập các mệnh đề C trên tập các biến U.

- Câu hỏi: Có tồn tại một phép gán thỏa được cho C không?

Ví dụ: U = {u1, u2} và

C = {c1, c2} với c1 = {u1, }; c2 = { , u2}

}, { }} thì kết quả sẽ là Câu trả lời là “yes”. Một phép gán thỏa được đó là: t(u1) = t(u2) = T. Trong trường hợp, ta thay C bởi C’ = {{u1, u2}, {u1,

“no”, do đó C’ là không thỏa được.

Định lý Cook. SAT là NP-đầy đủ.

Chứng minh:

i) SAT thuộc NP

Dễ dàng thấy được là SAT thuộc NP. Một thuật toán không tất định để giải bài

toán SAT chỉ cần phỏng đoán một phép gán t và kiểm tra xem phép gán t có thoả mãn

tập mệnh đề C không. Điều này dễ dàng thực hiện trong thời gian đa thức.

ii) Tồn tại một biến đổi đa thức fL từ mỗi bài toán  trong NP về SAT

SAT được biểu diễn bởi một ngôn ngữ LSAT = L[SAT,e] với một lược đồ mã hoá

hợp lý e nào đó. Chúng ta phải chứng tỏ rằng với mọi ngôn ngữ L  NP, L  LSAT.

Ký hiệu M là một chương trình NDTM thời gian đa thức tuỳ ý, xác định bởi ,

*, b, Q, q0, qY, qN và p, đoán nhận ngôn ngữ L = LM. Ngoài ra, cho p(n) là một đa thức

trên tập các số nguyên, nó giới hạn hàm phức tạp thời gian TM(n). (Không mất tính tổng quát, ta có thể giả sử p(n)  n với mọi n  Z+). Phép biến đổi tổng quát fL sẽ nhận được dưới dạng M, , *, b, Q, q0, qY, qN,  và p.

fL có tính chất là đối với mọi x  *, x  L nếu và chỉ nếu fL(x) có một phép gán

thoả được. Điểm mấu chốt khi xây dựng fL là cho thấy cách mà tập các mệnh đề được

sử dụng để kiểm tra xem một đầu vào x có được chấp nhận bởi chương trình NDTM là

M không, tức là x  L không.

Nếu đầu vào x được chấp nhận bởi M, thì chúng ta biết rằng có một tính

toán chấp nhận được cho M trên x sao cho cả số bước trong giai đoạn kiểm tra và số ký

hiệu trong xâu phỏng đoán giới hạn bởi p(n) với n = |x|. Một tính toán như vậy sẽ chỉ

liên quan đến các ô được đánh số từ -p(n) tới p(n)+1, vì đầu đọc-ghi bắt đầu từ ô 1 di

chuyển tối đa là một ô tại mỗi bước chuyển. Trạng thái của việc tính toán kiểm tra tại

một thời điểm có thể được xác định hoàn toàn, bằng cách đưa ra nội dung của các ô

này, trạng thái hiện tại, và vị trí của đầu đọc-ghi. Hơn nữa, vì có không nhiều hơn p(n)

bước trong việc tính toán kiểm tra, có nhiều nhất là p(n) +1 thời điểm riêng biệt phải

xem xét. Điều này cho phép chúng ta mô tả một tính toán như vậy một cách đầy đủ, chỉ

sử dụng một số giới hạn các biến Boolean và một phép gán cho chúng.

Gán nhãn các phần tử của Q là q0, q1 = qY, q2 = qN, q3, ..., qr với r = |Q|-1 và gán

nhãn các phần tử của |-1. Sẽ có ba loại biến, từng loại là s0 = b, s1, s2, ..., sv với v = |

có một ý nghĩa cụ thể xác định ở Hình 3. Cụm từ “tại thời điểm i” có nghĩa là “trong

lúc thực hiên bước i của việc tính toán kiểm tra”.

Phạm vi Ý nghĩa Biến

0 i p(n) Q[i,k] Tại thời điểm i, M ở trạng thái qk 0 k r

p(n) Tại thời điểm i, đầu đọc-ghi đang 0 i H[i,j] -p(n) p(n) + 1 đọc ô j j

0 i p(n) Tại thời điểm i, nội dung của ô j là S[i,j,k] -p(n) p(n) + 1 j ký hiệu sk 0 k v

Hình 3. Các biến trong fL(x) và ý nghĩa của chúng.

Một tính toán của M sẽ tạo ra một phép gán cho các biến này một cách ràng, với

quy ước là nếu chương trình dừng trước thời gian p(n) thì cấu hình vẫn giữ nguyên ở

tất cả thời điểm tiếp theo, giữ nguyên trạng thái dừng, ví trí đầu đọc-ghi và nội dung

băng. Nội dung của băng tại thời điểm 0 chứa đầu vào x được viết trong các ô từ 1 đến

n, và xâu phỏng đoán w được viết trong các ô từ -1 đến -|w|, các ô còn lại là trống.

Theo một phép gán tùy ý, một ô cho trước có thể chứa nhiều kí hiệu tại một

thời điểm, máy có thể cùng lúc ở vài trạng thái khác nhau, và đầu đọc-ghi có thể ở

trong tập con bất kỳ của các vị trí –p(n) tới p(n)+1. Biến đổi fL làm việc bằng cách xây

dựng một tập các mệnh đề liên quan đến các biến này sao cho một phép gán là thoả

được nếu và chỉ nếu nó là phép gán được tạo ra bởi một tính toán chấp nhận được cho

x mà giai đoan kiểm tra có p(n) bước hoặc ít hơn, và xâu phỏng đoán có độ dài tối đa

p(n). Vì vậy ta sẽ có:

x  L  có một tính toán chấp nhận được của M trên x

 có một tính toán chấp nhận được của M trên x với p(n) bước hoặc ít hơn

trong giai đoạn kiểm tra và với xâu được đoán có độ dài chính xác bằng p(n).

 có một phép gán thỏa được cho tập mệnh đề trong fL(x).

Điều này có nghĩa là fL thỏa mãn một trong hai điều kiện yêu cầu của một biến

đổi đa thức. Điều kiện còn lại là fL có thể được thực hiện trong thời gian đa thức, sẽ

được kiểm chứng một cách dễ dàng một khi chúng ta đã hoàn thành mô tả về fL.

Các mệnh đề trong fL(x) có thể phân chia thành sáu nhóm, mỗi nhóm áp đặt một

loại hạn chế riêng biệt trên phép gán thoả được bất kỳ như trong Hình 4.

Nhóm mệnh đề Hạn chế được áp đặt

Tại thời điểm i, M ở chính xác một trạng thái. G1

Tại thời điểm i, đầu đọc-ghi đọc chính xác một ô. G2

Tại thời điểm i, mỗi ô chứa chính xác một ký hiệu G3 của .

Tại thời điểm 0, tính toán ở cấu hình ban đầu với sự G4 kiểm tra của đầu vào x.

Trước thời gian p(n), M đã vào trạng thái là qY và do G5 đó đã chấp nhận x.

Mỗi thời điểm i, 0 i < p(n), cấu hình của M tại

thời điểm i+1 theo sau bởi một áp dụng duy nhất của G6

hàm chuyển  từ cấu hình tại thời điểm i.

Hình 4. Các nhóm mệnh đề trong fL và các hạn chế áp đặt trên phép gán.

Nhận xét rằng, nếu tất cả sáu nhóm mệnh đề đều thực hiện nhiệm vụ dự định

của chúng thì một phép thực trị thoả được sẽ phải tương ứng với tính toán chấp nhận

mong muốn cho x. Vì vậy, chúng ta chỉ cần chứng tỏ rằng cách mà các nhóm mệnh đề

thực hiện nhiệm vụ của chúng là có thể xây dựng được.

Nhóm G1 bao gồm những mệnh đề sau:

{Q[i,0], Q[i,1], ..., Q[i,r]}, 0  i  p(n)

{ , }, 0  i  p(n), 0  j < j’ r

(p(n) + 1) mệnh đề đầu tiên có thể đồng thời được thỏa mãn nếu và chỉ nếu, tại

mỗi thời điểm i, M ở trong ít nhất một trạng thái. (p(n) + 1)(r + 1)(r/2) mệnh đề còn lại

có thể đồng thời thỏa mãn nếu và chỉ nếu không có thời điểm i nào mà M ở nhiều hơn

một trạng thái. Do đó thực hiện nhiệm vụ của nó.

Nhóm G2 và G3 được xây dựng tương tự, và nhóm G4 và G5 đều khá đơn giản

mỗi nhóm chỉ bao gồm các mệnh đề một literal. Hình 6 mô tả đầy đủ năm nhóm đầu

tiên. Chú ý rằng số mệnh đề trong các nhóm, và số literals lớn nhất xuất hiện trong mỗi

mệnh đề đều bị chặn bởi hàm đa thức của n (vì r và v là các hằng số xác định bởi M, do

đó bởi L).

Nhóm mệnh đề cuối cùng G6, đảm bảo rằng mỗi cấu hình tiếp theo trong tính

toán theo sau cấu hình trước đó bởi một bước của chương trình M, là phức tạp hơn một

chút. Nó bao gồm hai nhóm con các mệnh đề.

Nhóm con đầu tiên đảm bảo rằng nếu đầu đọc-ghi không quét ô j tại thời điểm i,

thì kí hiệu trong ô j không thay đổi giữa thời điểm i và i+1. Những mệnh đề trong

nhóm con này như sau:

{ , H[i,j], S[i+1,j,l]}, 0  i < p(n), -p(n)  j  p(n)+1, 0  l  v

Với mỗi thời điểm i, ô j và kí hiệu sl, nếu đầu đọc-ghi không quét ô j tại thời

điểm i và ô j chứa sl tại thời điểm i nhưng không chứa tại thời điểm i+1 thì mệnh đề ở

trên dựa trên i, j và l sẽ không thỏa được (ngược lại thì nó sẽ thỏa được). Do đó, 2(p(n)+1)2(v+1) mệnh đề trong nhóm con này sẽ thực hiện nhiệm vụ của chúng.

Nhóm mệnh đề Các mệnh đề trong nhóm

{Q[i,0], Q[i,1], ..., Q[i,r]}, 0 ≤ i ≤ p (n) G1

}, 0 ≤ i ≤ p(n), 0 ≤ j < j’ ≤ r , {

{H[i,-p(n)], H[i,-p(n)+1], ..., H[i,p(n)+1]}, 0 ≤ i ≤ p(n) G2

}, 0 ≤ i ≤ p(n), -p(n) ≤ j < j’ ≤ p(n)+1 , {

{S[i,j,0], S[i,j,1],...., S[i,j,v]}, 0 ≤ i ≤ p(n), -p(n) ≤ j≤ p(n)+1 G3

, }, 0 ≤ i ≤ p(n), -p(n) ≤ j ≤ p(n)+1, 0 ≤ k≤ k’≤ v {

{Q[0,0]}, {H[0,1]}, {S[0,0,0]}, G4

{S[0,1,k1]}, {S[0,2,k2]}, …, {S[0,n,kn]},

{S[0,n+1,0]}, {S[0,n+2,0]}, …, {S[0,p(n)+1,0]}

trong đó x =

{Q[p(n),1]} G5

Hình 5. Năm nhóm mệnh đề đầu tiên trong fL(x).

Nhóm con còn lại của G6 đảm bảo những chuyển đổi từ một cấu hình sang cấu

hình tiếp theo phù hợp với hàm chuyển  cho M.

Với mỗi bộ (i, j, k, l), 0 ≤ i < p(n), -p(n) ≤ j ≤ p(n)+1, 0 ≤ k ≤ r, và 0 ≤ l ≤ v,

nhóm con này gồm có các mệnh đề sau:

, ], , H[i+1, j+ ]} {

, ], , Q[i+1, k’]} {

, ], , S[i+1, j,l’]} {

trong đó nếu qk  Q-{qy, qN} thì giá trị của , k’, l’ thoả mãn (qk, sl) = (qk’, sl’, ), và nếu qk {qY, qN} thì  = 0, k’ = k và l’ = l.

Không khó để thấy rằng 6(p(n))(p(n) + 1)(r + 1)(v + 1) mệnh đề này áp đặt

những hạn chế mong muốn trên các phép gán thoả được.

Vì vậy, ta đã cho thấy cách xây dựng các nhóm mệnh đề từ G1 tới G6 thực hiện

các nhiệm vụ được nói ở trên. Nếu x  L thì có một tính toán chấp nhận của M trên x

có chiều dài p(n) hoặc ít hơn, và tính toán này bắt buộc một phép gán phải thoả mãn tất

cả các mệnh đề trong C = G1  G2  G3  G4  G5  G6.

Ngược lại, việc xây dựng C là một phép gán thoả được cho C phải tương ứng

với một tính toán chấp nhận của M trên x. Nó kéo theo là fL(x) có một phép gán thỏa

được nếu và chỉ nếu x  L.

Tất cả những gì còn cần chứng tỏ là đối với bất kỳ ngôn ngữ L cố định, fL(x) có

thể được xây dựng từ x trong thời gian bị chặn bởi một hàm đa thức của n = |x|. Cho

trước L, chúng ta chọn một chương trình NDTM nào đó là M đoán nhận L trong thời

gian bị chặn bởi một đa thức p. Giới hạn đa thức của việc tính toán tập các biến U và

tập mệnh đề C được suy trực tiếp một khi chúng ta chứng tỏ rằng Length[fL(x)] là bị

chặn trên bởi một hàm đa thức của n, trong đó Length[I] là độ dài của một chuỗi mã

hóa thể hiện I theo một lược đồ mã hoá hợp lý. Hàm Length “hợp lý” như vậy cho SAT

được cho trước, chẳng hạn bằng |U|.|C|. Không mệnh đề nào có thể chứa nhiều hơn

2.|U| literal (đó là tổng số literal), và số ký hiệu cần thiết để mô tả mỗi literal được giới

hạn đa thức. Vì r và v được cố định trước và chỉ có thể thêm vào các hằng số vào |U| và |C|, chúng ta có |U| = O(p(n)2) và |C| = O(p(n)2). Do đó, Length[fL(x)] = |U|.|C| = O(p(n)4), và được giới hạn bởi một hàm đa thức của n như mong muốn.

Vì vậy, biến đổi fL có thể tính được bởi một thuật toán thời gian đa thức và ta

kết luận rằng với mỗi L  NP, fL là một biến đổi đa thức từ L về SAT. Vậy SAT là NP-

đầy đủ.

2) Bài toán 3-SATIFIABILITY (3SAT)

Bài toán 3SAT là một biến thể hạn chế của bài toán SAT trong đó mỗi mệnh đề

chỉ chứa đúng ba literal. Cấu trúc đơn giản của 3SAT làm cho nó trở thành một trong

các bài toán được sử dụng rộng rãi để chứng minh các kết quả NP-đầy đủ khác.

- Đầu vào: Cho tập các mệnh đề C = {c1, c2, ..., cm} dựa trên một tập hữu hạn

các biến U sao cho |ci| = 3 với 1  i  m.

- Câu hỏi: Có tồn tại một phép gán cho U mà thỏa mãn tất cả các mệnh đề trong

C?

Định lý. 3SAT là NP-đầy đủ.

i) 3SAT  NP

Dễ dàng thấy rằng 3SAT thuộc lớp NP vì thuật toán không tất định chỉ cần

phỏng đoán một phép gán cho các biến và kiểm tra trong thời gian đa thức phép gán đó

thỏa được tất cả các mệnh đề có 3 literal đã cho không.

ii) Ta sẽ xây dựng một phép biến đổi SAT thành 3SAT

Giả sử ta có một đầu vào của SAT là I = (U,C) với U = {u1, ..., un} là tập các

biến và C = {c1, ..., cm} là tập các mệnh đề trên U.

Chúng ta sẽ xây dựng một phép biến đổi biến đầu vào của bài toán SAT là I thành đầu vào của bài toán 3SAT là I’ = (U’,C’). Tập C’ chỉ chứa các mệnh đề có đúng 3 literal trên tập các biến U’, sao cho C’ là thỏa được nếu và chỉ nếu C là thỏa được.

’.

Việc xây dựng C' đơn giản là chỉ cần thay thế mỗi mệnh đề riêng biệt cj thuộc C ’ “tương đương” thuộc C’, dựa trên các biến trong U và một bởi một tập các mệnh đề Cj

’ chỉ được sử dụng trong các mệnh đề Cj

vài biến bổ sung thêm Uj

Ta có thể biểu diễn điều này như sau:

và

’ và Uj

’ từ cj.

Vì thế, ta chỉ cần chỉ ra cách xây dựng Cj

Giả sử cj = {z1, z2, ..., zk} với các zi là tất cả literal có thể được dẫn xuất từ các

biến trong tập U. Cách mà Cj' và Uj

2}

' được xây dựng phụ thuộc vào giá trị của k. ' = { yj

1, yj

1,

2},

Trường hợp 1: k = 1: Uj

1, yj

2}, {z1, yj

Cj' = {{z1, yj }, {z1, , yj

, }} {z1,

1}

Trường hợp 2: k = 2: Uj' = {yj

1}, {z1, z2,

}} Cj' = {{z1, z2, yj

Trường hợp 3: k = 3: Uj' = ; Cj' = {{cj}}

i : 1 i k-3}

1)}}  {{

i+1: 1 i k-4}}

Trường hợp 4: k > 3: Uj' = {yj

Cj' = {{z1, z2, yj , zi+2, yj

{{ , zk-1, zk}}

Tiếp theo, để chứng minh rằng phép biến đổi ở trên là đúng đắn, chúng ta sẽ

phải chứng tỏ được rằng tập C’ thỏa được nếu và chỉ nếu tập C thỏa được.

biến trong mỗi Uj

’ ở các mệnh đề Cj

gán t có thể được mở rộng thành các tập Uj

- C thỏa được thì C’ cũng thỏa được: Giả sử rằng cho C thỏa được bởi phép gán t: U  {T,F}. Ta chứng tỏ rằng t có thể được mở rộng thành phép gán t’: U’  {T,F} thỏa được cho C’. Bởi vì các biến trong U’-U được phân chia vào các tập Uj ’ và các ’, nên ta chỉ cần chỉ ra phép ’ chỉ xuất hiện trong các mệnh đề thuộc Cj ’ như thế nào, và trong ’ tương ứng mỗi trường hợp ta chỉ cần xác nhận lại rằng tất cả các mệnh đề trong tập Cj

’ luôn thỏa được bởi t. Vì vậy chúng ta có thể

đó là thỏa được. Chúng ta có thể làm như sau:

’).

Với k ≤ 2: thì các mệnh đề trong Cj

’ (cho t’(y) = T với mọi y  Uj

mở rộng t tùy ý cho Uj

’ là thỏa được bởi t.

’ là rỗng và mệnh đề trong Cj

Với k = 3: thì Uj

Với k > 3: Vì t là một phép gán thỏa được cho C, nên phải có ít nhất một số

nguyên l sao cho literal zl là True bởi t.

i) = F với 1 ≤ i ≤ k-3).

 Nếu z1 hoặc z2 là True (tức là l = 1 hoặc l = 2) thì ta gán giá trị của các biến bổ

sung là “False” (t’(yj

 Nếu zk-1 hoặc zk là True (tức là l = k-1 hoặc k) thì ta gán giá trị của các biến bổ

i) = F

i) = T với 1 ≤ i ≤ k-3).  Các trường hợp còn lại, ta gán giá trị t’(yj

i) = T với 1 ≤ i ≤ l-2 và gán t'(yj

sung là “True” (t’(yj

với l-1 ≤ i ≤ k-3.

mệnh đề Cj

Dễ dàng để xác định rằng những trường hợp lựa chọn này đảm bảo tất cả các ’ đều thỏa được, vì vậy tất cả các mệnh đề trong C’ sẽ thỏa được theo t’. - Ngược lại, nếu t’ là một phép gán thỏa được cho C’, dễ dàng để xác định rằng sự thu hẹp của t’ chỉ cho các biến trong U là một phép gán thỏa được cho C. Do đó C’

là thỏa được nếu và chỉ nếu C thỏa được.

iii) Phép biến đổi này có thể được thực hiện trong thời gian đa thức

Có: |U| = n; |C| = m

Trường hợp 1: tạo 4 mệnh đề mới

Trường hợp 2: tạo ra 2 mệnh đề mới

Trường hợp 3: tạo ra 1 mệnh đề mới

Trường hợp 4: tạo ra k-1 mệnh đề mới, với k là số lượng các literal trên mỗi

mệnh đề  I.

Do đó có tổng cộng m*(k-1) mệnh đề mới trong I’. Vì k  2n nên có nhiều nhất 2mn mệnh đề trong I’. Vì số lượng các mệnh đề trong C’ bị giới hạn bởi hàm đa thức

2mn. Do đó, kích thước của thể hiện 3SAT bị giới hạn trên bởi một hàm đa thức với

kích thước của thể hiện SAT. Không khó để xác định rằng đây là một phép biến đổi đa

thức.

3) Bài toán 3-DIMENSIONAL MATCHING (3DM)

Bài toán đối sánh 3 chiều xuất phát từ bài toán cổ "Bài toán hôn nhân": Cho n

người đàn ông và n phụ nữ, tất cả đều chưa lập gia đình cùng với một danh sách tất cả

các cặp nam nữ sẵn sàng hôn nhân, liệu rằng có thể để sắp xếp được n cuộc hôn nhân

sao cho tránh được chế độ đa thê (đa phu) và tất cả mọi người đều nhận được một

người chồng (vợ) có thể chấp nhận.

Tương tự, trong bài toán 3DM các tập W, X, và Y tương ứng với 3 giới tính

khác nhau, và mỗi cặp ba trong tập M tương ứng với cuộc hôn nhân 3 người mà có thể

chấp nhận được với cả 3 người tham gia. Nhận xét rằng bài toán 3DM là NP-đầy đủ,

còn bài toán hôn nhân thông thường có thể giải được trong thời gian đa thức.

Bài toán 3DM có thể mô tả như sau:

- Đầu vào: Một tập M  W x X x Y; với W, X, và Y là các tập rời nhau và đều

có q phần tử.

- Câu hỏi: M có chứa một đối sánh là một tập con M’  M sao cho |M’| = q và

không có bất kì hai phần tử nào của M’ có chung thành phần với nhau?

Định lý. 3DM là NP-đầy đủ.

Chứng minh:

i) 3DM  NP

Dễ dàng thấy rằng 3DM thuộc NP, vì thuật toán không tất định chỉ cần dự đoán

một tập con từ tập M có q = |W| = |X| = |Y| các bộ ba và kiểm tra trong thời gian đa

thức rằng không có hai bộ ba nào có chung thành phần.

ii) Chúng ta sẽ xây dựng phép biến đổi 3SAT về 3DM

Cho một đầu vào của 3SAT là I = (U,C), với U = {u1, u2, ..., un} là tập các biến

và C = {c1, c2, ..., cm) là tập các mệnh đề.

Chúng ta phải xây dựng một phép biến đổi chuyển dữ kiện trên thành dữ kiện

tương ứng của bài toán 3DM gồm các tập rời nhau W, X, và Y với |W| = |X| = |Y| và

tập M  W x X x Y sao cho M có chứa một đối sánh nếu và chỉ nếu C là thỏa được.

Tập M chứa các bộ ba có thứ tự sẽ được phân chia vào ba lớp (thành phần) riêng

biệt, và nhóm lại theo chức năng dự định của chúng là: “truth-setting and fan-out”,

“satisfaction testing”, hoặc “garbage collection”.

Thành phần TSFO (truth-setting and fan-out)

Mỗi thành phần TSFO tương ứng với một biến ui  U, và cấu trúc của nó phụ

thuộc vào tổng số m các mệnh đề trong C.

Trong đó, thành phần TSFO cho mỗi biến ui bao gồm các phần tử "bên trong"

ai[j]  X và bi[j]  Y, l ≤ j ≤ m, các phần tử này không xuất hiện trong bất kỳ bộ ba

 W, 1 ≤ j ≤ m, nào bên ngoài thành phần này, và các phần tử “bên ngoài" ui[j],

các phần tử này sẽ xuất hiện trong các bộ ba khác.

t = {(

Các bộ ba tạo nên thành phần này có thể được chia thành 2 tập sau:

Ti , ai[j], bi[j]): 1 ≤ j ≤ m}

f = {( ui[j], ai[j+1], bi[j]): 1 ≤ j < m}  {(ui[m], ai[1], bi[m])}

Ti

t  Tf

Vì các phần tử bên trong {ai[j], bi[j]): 1 ≤ j ≤ m } sẽ không xuất hiện trong bất

= Ti

i, nên dễ dàng thấy rằng bất kỳ đối sánh M’ nào t , hoặc tất cả

kỳ bộ ba nào bên ngoài tập Ti

i ). Do đó chúng ta có thể coi thành phần Ti là một bắt buộc khi một đối

t .

đều bao gồm chính xác m bộ ba từ tập Ti (hoặc tất cả bộ ba đều thuộc Ti đều thuộc tập Tf

sánh chọn lựa thiết lập ui true hay false. Như vậy, một đối sánh M'  M xác định một phép gán cho U, với biến ui được thiết lập true nếu và chỉ nếu M’ ∩ Ti = Ti

Thành phần ST (satisfaction testing)

Mỗi thành phần kiểm tra tính thỏa được trong M tương ứng với một mệnh đề

cj C. Nó chỉ bao gồm hai phần tử "bên trong" s1[j] X và s2[j]Y, và các phần tử bên

ngoài {ui[j], : 1 ≤ i ≤ n} được xác định bởi các literal xuất hiện trong mệnh đề cj. Tập

các bộ ba tạo nên thành phần này được định nghĩa như sau:

Cj = {(ui[j], s1[j], s2[j]): ui  cj}  {( , s1[j], s2[j]):  cj}

Vì vậy, bất kỳ đối sánh M'  M nào đều phải chứa chính xác một bộ ba từ tập

Cj. Tuy nhiên, điều này chỉ có thể được thực hiện nếu ui[j] (hoặc ) của literal ui cj

(  cj ) không xuất hiện trong các bộ ba thuộc Ti ∩ M’, nghĩa là nếu và chỉ nếu phép

gán xác định bởi M là thoả được mệnh đề cj.

Thành phần GC (garbage collection)

Việc xây dựng được hoàn thành bởi một thành phần GC lớn là G, gồm có các

phần tử bên trong g1[k] X và g2[k]  Y, 1 ≤ k ≤ m(n-1), và các phần tử bên ngoài ui[j]

và từ W. Nó là tập các bộ ba như sau:

G = {(ui[j], g1[k], g2[k]),( , g1[k], g2[k]):

1 ≤ k ≤ m(n-1), 1 ≤ i ≤ n, 1 ≤ j ≤ m}

, và không Như vậy mỗi cặp g1[k], g2[k] phải ghép với duy nhất ui[j] hoặc

xuất hiện trong bất kỳ bộ ba nào thuộc M’ - G.

Như vậy G chỉ đơn thuần đảm bảo rằng, bất cứ khi nào một tập con của M - G

thỏa mãn tất cả các ràng buộc bởi các thành phần TSFO, thì tập con đó có thể được mở

rộng thành một đối sánh cho M.

Tóm lại, chúng ta thiết lập được các tập W, X, Y và M như sau:

): 1≤ i ≤ n,1 ≤ j ≤ m} W = {(ui[j],

X = A  S1  G1

trong đó:

A = {ai[j]: 1≤ i ≤ n,1 ≤ j ≤ m}

S1 = {s1[j]: 1 ≤ j ≤ m}

G1 = {g1[j]: 1 ≤ j ≤ m(n-1)}

Y = B  S2  G2

trong đó:

B = {ai[j]: 1≤ i ≤ n,1 ≤ j ≤ m}

S2 = {s1[j]: 1 ≤ j ≤ m}

G2 = {g1[j]: 1 ≤ j ≤ m(n-1)}

và

M =

Chú ý rằng mỗi bộ ba thuộc M là một phần tử thuộc W x X x Y theo yêu cầu. Hơn nữa, vì M chỉ chứa 2mn + 3m + 2m2n(n-1) bộ ba, nên dễ dàng thấy rằng M có thể

được xây dựng trong thời gian đa thức.

iii) Bây giờ ta phải chỉ ra phép biến đổi trên là đúng đắn bằng việc chứng minh

M chứa một đối sánh M’ nếu và chỉ nếu C thỏa được.

- Chứng minh C thỏa được thì M chứa một đối sánh M’ nào đó

Cho t: U→{T,F} là phép gán thỏa được bất kì cho C. Chúng ta xây dựng một

đối sánh M'  M như sau:

Đối với mỗi mệnh đề cj  C, lấy zj  {ui,

: 1 ≤ i ≤ n} ∩ cj là một literal được thiết lập giá trị true bởi t (phải tồn tại vì t thỏa được cj). Một tập M’ có cấu trúc như sau

trong đó G’ là tập con của G được chọn một cách chính xác, nó bao gồm tất cả

còn lại. g1[k], g2[k] và các ui[j] và

Dễ dàng kiểm tra lại rằng tập G’ như vậy luôn có thể chọn được và kết quả là M’

là một đối sánh.

- Chứng minh M chứa một đối sánh M’ thì C thỏa được Giả sử ta có một đối sánh M’ thuộc M (với việc xây dựng như trên).

f thì t(ui) = False, t(

) = True.

+ Nếu Ti ∩ M’ = Ti Mặt khác, do điều kiện khi xây dựng đối sánh M’ nên lựa chọn bộ ba thuộc Cj

f chứa các bộ ba có chứa phần tử ui[j]), nên cj thỏa được.

phải chứa (vì Ti

t thì t(ui) = True, ta cũng lập luận tương tự thì cj thỏa

+ Còn nếu như Ti ∩ M’ = Ti

được.

Do vậy C là thỏa được.

4) Bài toán VERTEX COVER (VC)

- Đầu vào: Cho đồ thị G = (V,E) và số nguyên dương k thoả mãn k  |V|

- Câu hỏi: Tồn tại hay không một tập con V’ của V sao cho |V’|  k và mỗi cạnh

{u, e}  E thì một trong hai đỉnh u hoặc e phải thuộc V’.

Định lý. VC là NP-đầy đủ

i) VC  NP

Dễ dàng thấy rằng VC thuộc NP, vì thuật toán không tất định chỉ cần dự đoán

một tập con của tập đỉnh và kiểm tra trong thời gian đa thức rằng tập con đó có chứa ít

nhất một đầu của mỗi cạnh và có kích thước phù hợp.

ii) Chúng ta sẽ xây dựng phép biến đổi 3SAT về VC

Cho một đầu vào của 3SAT là I = (U,C), với U = {u1, u2, ..., un} là tập các biến

và C = {c1, c2, ..., cm) là tập các mệnh đề.

Chúng ta phải xây dựng một đồ thị G = (V,E) và một số nguyên dương K  |V|

sao cho G có một phủ đỉnh kích thước K hoặc bé hơn nếu và chỉ nếu C thoả được.

Với mỗi biến ui  U, có một thành phần “truth-setting” là Ti = (Vi,Ei) với

}}, tức là hai đỉnh được nối bởi một cạnh. Chú ý rằng bất kỳ Vi={ui, } và Ei = {{ui,

’),

phủ đỉnh nào cũng sẽ chứa ít nhất ui hoặc để phủ cạnh duy nhất trong Ei.

’,Ej

Với mỗi mệnh đề cj  C, có một thành phần “satisfaction test” là Sj = (Vj

bao gồm 3 đỉnh và 3 cạnh kết nối chúng tạo thành một tam giác:

Vj

’ = {a1[j],a2[j],a3[j]} ’ = {{ a1[j],a2[j]}, {a1[j],a3[j]}, {a2[j],a3[j]}}

’ để phủ

Ej

’.

Chú ý rằng bất kỳ phủ đỉnh nào cũng sẽ chứa ít nhất hai đỉnh trong Vj

các cạnh trong Ej

Phần còn lại của việc xây dựng là tập các cạnh kết nối. Với mỗi mệnh đề cj  C,

ký hiệu các literal trong cj là xj, yj và zj. Khi đó các cạnh kết nối bắt nguồn từ Sj được

cho bằng:

” = {{a1[j],xj},{a2[j],yj},{a3[j],zj}}

Ej

Việc xây dựng thể hiện của VC được hoàn thành bằng cách thiết lập K = n + 2m

và G = (V,E) trong đó:

V =

và

E =

Dễ dàng thấy rằng cách xây dựng này có thể thực hiện trong thời gian đa thức.

Còn phải chứng tỏ rằng C là thoả được nếu và chỉ nếu G có một phủ đỉnh kích thước K

hoặc bé hơn.

Trước hết, giả sử V’  V là một phủ đỉnh của G với |V’|  K. Theo các chú ý ở trên thì V’ phải chứa ít nhất một đỉnh từ mỗi Ti và chứa ít nhất hai đỉnh từ mỗi Sj. Như vậy tổng số ít nhất là n + 2m = K đỉnh, nên thực sự là V’ chứa chính xác một đỉnh từ mỗi Ti và chính xác hai đỉnh từ mỗi Sj. Do đó chúng ta có thể sử dụng cách mà V’ giao

với thành phần “truth-setting” để thu được phép gán t: U{T,F}. Chúng ta chỉ cần cho

t(ui) = T nếu ui V’ và t(ui) = F nếu V’.

ba cạnh trong Ej

Để thấy rằng phép gán này là thoả được tất cả các mệnh đề cjC, ta hãy xem xét ”. Chỉ có hai cạnh trong chúng có thể được phủ bởi các đỉnh thuộc ’V’, vì vậy một cạnh trong chúng phải được phủ bởi một đỉnh trong Vi V’. Nhưng Vj

điều này có nghĩa rằng literal tương ứng là ui hoặc trong mệnh đề cj là đúng theo t,

và do đó mệnh đề cj là thoả được bởi t. Bởi vì điều này là đúng với mọi cj nên suy ra

rằng t là phép gán thoả được cho C.

Ngược lại, giử sử rằng t: U{T,F} là một phép gán thoả được cho C. Phủ đỉnh tương ứng V’ bao gồm một đỉnh từ mỗi Ti và hai đỉnh từ mỗi Sj. Đỉnh từ Ti thuộc V’ là

ui nếu t(ui) = T, và là

”, và đây chính là phủ đỉnh mong muốn.

nếu t(ui) = F. Điều này đảm bảo rằng ít nhất một trong ba cạnh ” được phủ, bởi vì t thoả được các cj. Vì vậy, ta chỉ cần bao gồm trong V’ các của mỗi Ej

đỉnh cuối từ Sj của hai cạnh còn lại trong Ej

5) Bài toán CLIQUE

- Đầu vào: Cho đồ thị G = (V,E) và số nguyên dương k thoả mãn k  |V|

- Câu hỏi: Tồn tại hay không một tập con V’ của V sao cho |V’|  k mà mọi cặp

đỉnh trong V’ đều được nối bởi một cạnh trong E.

6) Bài toán HAMILTON CIRCUIL (HC)

Bài toán chu trình Hamilton là bài toán xác định xem với một đồ thị G = (V,E)

cho trước có chứa một chu trình Hamilton (chu trình đơn chứa mọi đỉnh của G). Bài

toán được phát biểu dưới dạng bài toán quyết định như sau:

- Đầu vào: Cho đồ thị G = (V,E)

- Câu hỏi: G có chứa một chu trình đơn đi qua mọi đỉnh hay không?

7) Bài toán PARTITION - Instance: Một tập hữu hạn A và một “trọng số” s(a)  Z+ cho mỗi a  A

- Question: Có tồn tại một tập con A’  A sao cho

8) Bài toán TRAVELING SALEMAN (TSP)

Bài toán người bán hàng được phát biểu dưới dạng bài toán đồ thị là:

Cho đồ thị G cùng tham số k nguyên, mỗi cạnh e của G có một trọng số nguyên

c(e). Câu hỏi đặt ra là có tồn tại một chu trình qua tất cả các đỉnh của G (mỗi đỉnh đúng

một lần) mà tổng trọng số các cạnh đã đi qua không vượt quá k không? Bài toán được

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

- Đầu vào: Cho tập n thành phố C = {c1,…,cm} với khoảng cách d(ci,cj)  Z+ và

một số nguyên dương B.

- Câu hỏi: Có tồn tại một hoán vị  trên {1, 2, ..., m} sao cho:

 B hay không?

Ta có sơ đồ để chứng minh một số bài toán là NPC như sau:

SAT

3SAT

3DM VC

PARTITION CLIQUE HC

TSP

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

KẾT LUẬN

Như vậy trong bản luận văn này, chúng tôi đã đi tìm hiểu một số khái niệm quan

trọng của lý thuyết thuật toán, lý thuyết độ phức tạp và phân lớp độ phức tạp của các

bài toán. Trong lý thuyết thuật toán còn những nội dung trọng tâm như các thuật toán

thông dụng và độ phức tạp của các thuật toán này, ... Trong lý thuyết độ phức tạp còn

những nội dung quan trọng như phương pháp giải các bài toán tối ưu tổ hợp và các

thuật toán xấp xỉ, xác suất, heuristics và ứng dụng của nó ... Trong thời gian tới chúng

tôi sẽ nghiên cứu tiếp những nội dung này.

TÀI LIỆU THAM KHẢO

Tiếng Việt

1. Nguyễn Hữu Điển, Một số bài toán về thuật toán, NXB Giáo dục, Hà Nội, 2005.

2. Phan Huy Khánh, Giáo trình Lý thuyết tính toán, ĐH Đà Nẵng, Đà Nẵng, 1999.

Tiếng Anh

3. Agrawal, M., Kayal, N. and Saxena, N. (2002). PRIMES is in P. Tech. Report Dept.

of Computer Science and Engineering. Indian Inst. of Technology Kanpur.

4. Ahuja, R.K., Magnanti, T.L. and Orlin, J.B. (1993). Network Flows. Theory,

Algorithms and Applications. Prentice–Hall.

5. Dietzfelbinger, M. (2004). Primality Testing in Polynomial Time. LNCS 3000.

Springer.

6. Garey, M.R. and Johnson, D.B. (1979). Computers and Intractability. A Guide to the

Theory of NP-Completeness. W.H. Freeman.

7. Homer, S. (2001). Computability and Complexity Theory. Springer.

8. Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2001). Introduction to Automata

Theory, Languages and Computation. Addison-Wesley Longman.

9. Ingo Wegener (2005). Complexity Theory. Springer.

10. Martello, S. and Toth, P. (1990). Knapsack Problems. Wiley.

11. Motwani, R. and Raghavan, P. (1995). Randomized Algorithms. Cambridge

University Press.

12. T. Cormen, C. Leiserson, R. Rivest (1990). Introduction to Algorithms, Mc Graw-

Hill.