Giáo trình Lý thuyết tính toán - Phan Huy Khánh
Tóm tắt Giáo trình Lý thuyết tính toán - Phan Huy Khánh: ...q3, q4} và P = { q1, 1 → #, R, q2, q2, 1 → # R, q3, q3, 1 → 1, R, q3, q3, # → 1, L, q4 } Nếu qui ước biểu diễn đơn nguyên (unary) của một số nguyên bởi viết liên tiếp n+1 chữ số 1 (số nguyên 0 được biểu diễn bởi một chữ số 1) và các cặp số nguyên biểu diễn theo quy ước này được đặt các...âu wi bị xóa khỏi băng thứ nhất để chép lại lên băng thứ hai. Băng thứ ba được ghi hằng q1_ . Khi kết thúc, máy TC ở cấu hình như sau : − Băng thứ nhất chứa câu f với đầu đọc-ghi nằm phía trái của f. − Băng thứ hai chứa câu wi với đầu đọc-ghi nằm phía trái của wi. − Băng thứ ba chứa câu q1... niệm trực giác với các máy Turing là một khái niệm hình thức. Do đó, ta cần hình thức hoá khái niệm về thủ tục hiệu quả. Nhưng khi đó, ta lại phải giải quyết vấn đề là có sự tương đương giữa phương pháp hình thức hoá đưa ra và khái niệm trực giác hay không ? Lời giải của vấn đề này lại nảy si...
các bài toán quyết định được thành những bài toán ít nhiều phức tạp hơn, không phụ thuộc vào hiện trạng của công nghệ Tin học. Có nhiều cách đo độ phức tạp tính toán đã được nghiên cứu, đó là độ phức tạp trung bình, độ phức tạp trong trường hợp xấu nhất, v. v... Dưới đây, ta sẽ chỉ xét độ phức tạp tính toán trong trường hợp xấu nhất. I. Độ phức tạp về thời gian và về bộ nhớ Người ta thường đưa vào khái niệm độ phức tạp cho các ngôn ngữ . Độ phức tạp của một bài toán là độ phức tạp của ngôn ngữ đặc trưng cho bài toán này. Ta xét một máy Turing đơn định có k băng và dừng trên mọi dữ liệu. Xuất phát từ một cấu hình ban đầu (1, q1, f), máy Turing có một tính toán dừng ở độ dài m. Ta xem rằng tập hợp Ln của tất cả các câu f cùng có một độ dài như nhau là n. Nếu Ln khác rỗng, với mỗi số nguyên n, ta cho kết hợp với số nguyên : T(n) = Maxf∈Ln { độ dài tính toán nhận biết f } Nếu Ln = ∅ (tập hợp trống), ta đặt T (n) = 0. Hàm T : N → N vừa định nghĩa xác định độ phức tạp về thời gian (time complexity) T(n) của máy Turing k băng (ta quy ước mỗi bước tính toán kéo dài trong một khoảng thời gian bằng đơn vị). Người ta cũng nói rằng ngôn ngữ được nhận biết bởi máy Turing có một độ phức tạp về thời gian nhiều nhất là T (n). 94 Lý thuyết tính toán Tương tự, ta xét một máy Turing off-line đơn định có k băng và dừng với mọi dữ liệu. Từ một cấu hình xuất phát (1, q1, f), máy này có một tính toán trên f và dừng. Trong quá trình tính toán, máy Turing di chuyển các đầu đọc-ghi của nó, mỗi một đầu đọc-ghi đến thăm một số ô phân biệt. Bây giờ ta xét tập hợp Ln của tất cả các câu f có cùng một độ dài n. Với mỗi số nguyên n, ta cho kết hợp với số nguyên : S (n) = Maxf∈Ln là số các ô đã được thăm trên các băng làm việc khi tính toán để nhận biết f . Nếu Ln = ∅, ta đặt S (n) = 0 Hàm S : N → N vừa định nghĩa xác định độ phức tạp về bộ nhớ (space complexity) S(n) của máy Turing 0ff-line k băng. Người ta nói rằng ngôn ngữ được nhận biết bởi máy Turing có một độ phức tạp về bộ nhớ nhiều nhất là S(n). Chú ý rằng khi xét độ phức tạp về bộ nhớ, người ta không xét không gian nhớ sử dụng trên băng đọc : không gian nhớ này đúng bằng độ dài n của câu cần nhận biết. Vì nếu không, người ta sẽ không thể nhận được hàm S(n). Sau đây, ký hiệu I (x) là phần nguyên của x, ta viết : T (n) = f (n) hàm T (n) được tăng lên max { n+1, I (f (n)) + 1 } S (n) = f (n) hàm S (n) được tăng lên max { 1, I (f (n) + 1 } Ví dụ 6.1 : Cho L = { w wR | w∈ {0, 1}* và wR là câu đảo của w } Tồn tại một máy Turing T1 có hai băng nhận biết ngôn ngữ L với chi phí về thời gian là T(n) = n + 1. Máy này sao chép lên băng thứ hai các ký tự đã đọc trên băng thứ nhất cho đến khi gặp ký tự rồi kiểm tra sự bằng nhau tương ứng của các ký tự tiếp theo trên băng thứ nhất với các ký tự đã ghi trên băng thứ hai nhưng theo chiều ngược lại. Rõ ràng, thời gian tính toán đúng bằng độ dài của câu cộng thêm một thời gian đọc ký tự # để kết thúc. Tồn tại một máy Turing T2 có hai băng nhận biết ngôn ngữ L có chi phí về bộ nhớ là S (n) = log2 (n). Máy này tính ghi theo hệ nhị phân trên băng thứ hai số các ký tự đã đọc trên băng thứ nhất cho đến khi gặp ký tự C, sau đó kiểm tra số ký tự kế tiếp ký tự này trên băng thứ nhất đúng bằng số ký tự vừa ghi trên băng thứ hai bằng cách giảm dần từng ký tự. Trường hợp thành công, máy kiểm tra từng đôi ký tự giống nhau cho tới một khoảng cách i của ký tự # ở mỗi phía, và kiểm tra tất cả các giá trị i cần thiết. Các giá trị này liên tiếp được ghi dưới dạng nhị phân trên băng thứ hai. Rõ ràng, không gian nhớ sử dụng trên băng thứ hai được tăng thêm một lượng là độ dài của câu dạng nhị phân, hay là logarit cơ số 2 của số nguyên này. Độ phức tạp tính toán 95 Như vậy, đối với các máy Turing không đơn định, có thể định nghĩa theo cách tương tự độ phức tạp tính toán không đơn định về thời gian và độ phức tạp tính toán không đơn định về bộ nhớ. Chỉ cần định nghĩa các hàm T (n) và S (n), cho trường hợp Ln ≠ ∅, như sau: T (n) = Maxf∈Ln { độ dài của tính toán ngắn nhất để nhận biết f } S (n) = Maxf∈Ln { số các ô đã được thăm trên băng khi tính toán một cách tiết kiệm nhất để nhận biết f } Rõ ràng, các định nghĩa đã đưa ra trong trường hợp các máy Turing đơn định chỉ là trường hợp đặc biệt của các định nghĩa về tính chất không đơn định này. II. Các lớp của độ phức tạp (Complexity classes) Trong mục trước, ta đã định nghĩa độ phức tạp của một ngôn ngữ cho trước. Ngược lại, bây giờ ta có thể xem xét họ các ngôn ngữ có một độ phức tạp đã cho. Giả sử f là một hàm tăng, ta có các định nghĩa sau : Ký hiệu Ý nghĩa DSPACE (f (n)) Họ các ngôn ngữ có độ phức tạp về bộ nhớ S (n) = f (n) NSPACE (f (n)) Họ các ngôn ngữ có độ phức tạp không đơn định về bộ nhớ S (n) = f (n) DTIME (f (n)) Họ các ngôn ngữ có độ phức tạp về thời gian T (n) = f (n) NTIME (f (n)) Họ các ngôn ngữ có độ phức tạp không đơn định về thời gian T (n) = f (n) Tất cả các họ trên được gọi là các lớp của độ phức tạp. Từ các định nghĩa trên, ta suy ra rằng : DSPACE (f (n)) ⊆ NSPACE (f (n)) DTIME (f (n)) ⊆ NTIME (f (n)) và, nếu f ≤ g, thì: DSPACE (f (n)) ⊆ DSPACE (g (n)) NSPACE (f (n)) ⊆ NSPACE (g(n)) DTIME (f (n)) ⊆ DTIME (g (n)) NTIME (f (n)) ⊆ NTIME (g(n)) Giả sử L là ngôn ngữ được cho trong ví dụ 6. 1 trước đây, ta có: L ∈ DTIME (n) ∩ DSPACE (log2 (n)), nhưng ta cũng có : L ∈ DTIME (n2) ∩ NTIME ( n) ∩ DSPACE (n) 96 Lý thuyết tính toán II.1. Hiện tượng nén Giả sử T là một máy Turing có độ phức tạp về bộ nhớ là S(n) = f(n), bằng cách sử dụng một bảng chữ trong đó, mỗi ký tự biểu diễn k ký tự liên tiếp của bảng chữ của T, ta có thể xây dựng một máy Turing T’ nhận biết cùng ngôn ngữ và có cùng độ phức tạp về bộ nhớ là f(n)/k. Máy T’ này mã hóa trên bảng chữ mới thông tin ghi trên mỗi một băng làm việc (nhớ rằng không kể không gian nhớ dùng để ghi dữ liệu vào). Rõ ràng, nhờ phương pháp này, bằng cách sử dụng một thừa số c không đổi, ta có thể giảm bớt độ phức tạp về bộ nhớ để nhận biết một ngôn ngữ đã cho. Nếu T là một máy Turing off-line có k băng, ta có thể nhận biết cùng một ngôn ngữ bằng cách sử dụng một máy Turing off−line chỉ có một băng, sử dụng cùng một phương pháp để không sử dụng không gian nhớ nhiều hơn T. Đối với độ phức tạp về bộ nhớ, việc ta giảm bớt số lượng băng làm việc không có nghĩa, cho nên, từ nay, ta chỉ xét đến các máy Turing off−line có một băng, thậm chí, trong trường hợp S(n) = n, ta chỉ xét các máy Turing có một băng mà không thêm gì nữa. Ta cũng có thể áp dụng phương pháp nén vừa trình bày trên đây đối với độ phức tạp về thời gian. Tuy nhiên phương pháp này không miễn đọc dữ liệu, mà cần một thời gian n + 1 để đọc dữ liệu có độ dài n. Như vậy, ta có thể giảm bớt nhờ một thừa số không đổi là c ngay khi T(n)/n có khuynh hướng tăng vô hạn. Bây giờ ta xem xét hiệu quả của độ phức tạp về thời gian khi giảm bớt số lượng các băng làm việc. Khi giảm bớt còn một băng, phân tích phương pháp đã trình bày ở chương 3 để chuyển từ k băng về một băng, ta chứng minh được : L ∈ DTIME (T (n)) ⇒ L được thừa nhận bởi một máy Turing một băng với chi phí thời gian là T2(n). Khi cần thực hiện việc sao chéo, ta có thể chuyển từ một băng sang hai băng nhằm làm giảm đáng kể số bước tính toán. Ta chứng minh được rằng việc rút gọn còn hai băng thay vì chỉ còn một băng làm tối ưu rõ rệt chi phí về thời gian : L ∈ DTIME (T (n)) ⇒ L được thừa nhận bởi một máy Turing có hai băng với thời gian T (n).log2(T (n)) Tuy nhiên, để trả lời câu hỏi : Với chi phí thời gian nhiều hơn (tương ứng : nhiều bộ nhớ hơn) thì người ta có nhận biết được thực sự nhiều ngôn ngữ hơn không ? ta có mệnh đề sau đây : Mệnh đề 6.1 : Với mọi hàm đệ quy toàn phần f, tồn tại một ngôn ngữ đệ quy L không thuộc họ DTIME (f (n)) (một cách tương ứng : không thuộc họ DSPACE (f (n))). Chứng minh : Sử dụng kỹ thuật đường chéo cho ngôn ngữ : L = { wi | Ti không thừa nhận câu wi sau f (|wi|) bước tính toán } Thật vậy, L là một ngôn ngữ đệ quy không thuộc họ DTIME (f (n)). Độ phức tạp tính toán 97 Giữa các phép đo độ phức tạp tính toán khác nhau này, ta có thể thiết lập các mối quan hệ. Một số quan hệ dễ dàng nhận được như sau : L ∈ DTIME (f (n)) ⇒ L ∈ DSPACE (f (n)) Thật vậy, máy Turing thăm một ô tại mỗi bước tính toán. Trường hợp xấu nhất xảy ra khi tất cả các ô đều khác nhau. L ∈ DSPACE (f (n)) và f (n) = log2 (n) ⇒ L ∈ DTIME (cf (n)) Thật vậy, nếu f (n) = log2 (n), tồn tại một hằng c sao cho cf(n) là lớn hơn số các cấu hình phân biệt có độ dài tối đa là f (n) của một máy Turing đã cho. L ∈ NTIME (f (n)) ⇒ L ∈ DTIME (cf (n)). Thật vậy, quan hệ này đến từ việc tăng thêm số cấu hình phân biệt đối với một dữ liệu có độ dài n. Thời gian tăng thêm là cf (n). Sau đây là một quan hệ được cho bởi định lý Savitch. Định lý Savitch WJ : L ∈ NSPACE (f (n)) và f (n) = log2 (n) ⇒ L ∈ DSPACE (f2 (n)). II.2. Các họ P, NP và P−bộ nhớ (P−space) Các lớp của độ phức tạp tính toán sau đây đủ quan trọng để có tên riêng : P = U 1i ≥ DTIME (ni), NP = U 1i ≥ NTIME (ni). Như vậy : P là lớp các ngôn ngữ được nhận biết bởi một máy Turing đơn định cần một lượng thời gian bậc đa thức, NP là lớp các ngôn ngữ được nhận biết bởi một máy Turing không đơn định cần một lượng thời gian bậc đa thức. Ta đưa vào các lớp P−bộ nhớ (P−space) và NP−bộ nhớ (NP−space) như sau : P−bộ nhớ = U 1i ≥ DSPACE (ni), NP−bộ nhớ = U 1i ≥ NSPACE (ni). P−bộ nhớ là lớp các ngôn ngữ được nhận biết bởi một máy Turing đơn định cần một lượng bộ nhớ bậc đa thức, NP−bộ nhớ là lớp các ngôn ngữ được nhận biết bởi một máy Turing không đơn định cần một lượng bộ nhớ bậc đa thức. Rõ ràng ta có đẳng thức : 98 Lý thuyết tính toán P−bộ nhớ = NP−bộ nhớ Và ta có các bao hàm sau đây : DSPACE (log2 (n)) ⊆ P ⊆ NP ⊆ P−bộ nhớ = NP−bộ nhớ. Trong thực tế, người ta ước lượng một bài toán là : − xử lý được (tractable), nếu bài toán đó thuộc lớp P hay giải được (workable) − không xử lý được (untractable), nếu bài toán đó không thuộc lớp P. hay không giải được (unworkable) Vì vậy, ít khi người ta giải quyết những bài toán cần một lượng thời gian và bộ nhớ dạng đa thức có bậc lớn hơn 4 vì sẽ làm tăng độ phức tạp tính toán. III. Rút gọn đa thức và các bài toán NP−đầy đủ III.1. Khái niệm Rút gọn đa thức (polynomial reduction) là làm mịn (refinement) khái niệm rút gọn số học đã định nghĩa ở chương 5. Ta vẽ lại sơ đồ rút gọn số học như sau : Hình 6.1 Rút gọn bài toán A về bài toán B Định nghĩa 6.1 Người ta nói bài toán A được rút gọn kiểu đa thức về bài toán B nếu tồn tại một máy Turing dừng cho mọi dữ liệu và thực hiện tính hàm f hết một lượng thời gian đa thức (polynomial time). Hàm f được xác định từ tập hợp các biểu diễn dữ liệu của bài toán A vào tập hợp các biểu diễn dữ liệu của bài toán B, thỏa mãn : w ∈ LA ⇔ f (w) ∈ LB Người ta nói rằng máy Turing này đã thực hiện kiểu đa thức (polynomially work) việc rút gọn bài toán A về bài toán B. Từ đó, ta có mệnh đề sau : Mệnh đề 6.2 : Nếu bài toán A được rút gọn kiểu đa thức về bài toán B, thì nếu B là một bài toán thuộc lớp P (một cách tương ứng : thuộc lớp NP), thì A cũng là một bài toán thuộc lớp P (một cách tương ứng : thuộc NP). Người ta cũng nói rằng các lớp P và NP là đóng đối với phép rút gọn đa thức. LPA S*\LPA LPB S*\LPB Anh của f từ các biểu diễn dữ liệu của bài toán A Biểu diễn dữ liệu của bài toán B Biểu diễn dữ liệu của bài toán A f f Độ phức tạp tính toán 99 Chứng minh : Thật vậy, giả sử T là một máy Turing luôn luôn dừng và nhận biết ngôn ngữ LB một lượng thời gian đa thức. Giả sử T’ là một máy Turing thực hiện việc rút gọn hết một lượng thời gian đa thức từ bài toán A về bài toán B. Rõ ràng, máy Turing T’ next T luôn luôn dừng và nhận biết ngôn ngữ LA một lượng thời gian đa thức. Một cách tương tự, ta định nghĩa khái niệm rút gọn sử dụng bộ nhớ logarit. Định nghĩa 6.2 : Người ta nói bài toán A được rút gọn về bài toán B cần một lượng bộ nhớ logarit nếu tồn tại một máy Turing luôn luôn dừng cho mọi dữ liệu và thực hiện tính hàm f sử dụng một lượng bộ nhớ theo logarit. Hàm f được xác định từ tập hợp các biểu diễn dữ liệu của bài toán A vào tập hợp các biểu diễn dữ liệu của bài toán B, thỏa mãn : w ∈ LA ⇔ f (w) ∈ LB Ta có mệnh đề sau : Mệnh đề 6.3 : Lớp P đóng đối với phép rút gọn sử dụng bộ nhớ logarit. Việc chuyển một chương trình RAM thành một chương trình của một máy Turing được thực hiện sao cho thời gian chạy của máy Turing được tính theo số bước tính toán, là một đa thức theo thời gian chạy chương trình của máy RAM được tính theo số các lệnh (instructions) đã thực hiện. Tương tự, việc chuyển một công thức trong một ngôn ngữ bậc cao thành một công thức của một máy RAM được thực hiện sao cho thời gian chạy công thức của máy RAM được tính theo số các lệnh của RAM đã thực hiện, là một đa thức về thời gian chạy công thức trên ngôn ngữ bậc cao, được tính theo số các lệnh đã thực hiện. Từ đó, việc định nghĩa các lớp P và NP được dựa trên mô hình các máy Turing nhưng không phụ thuộc chính xác vào mô hình này, và để đảm bảo rằng một ngôn ngữ là thuộc một trong hai lớp này, chỉ cần đếm số lượng các phép toán một cách đơn giản. III.2. Các bài toán cổ điển Sau đây là sáu bài toán cổ điển trong Tin học. 1. Bài toán tô màu các đỉnh của một đồ thị Dữ liệu : Một đồ thị G = và một số nguyên k. Câu hỏi : Ta có thể tô mỗi đỉnh của đồ thị một màu sao cho cứ hai đỉnh của đồ thị được nối với nhau bởi một cung thì không được tô cùng màu được chọn trong số k màu ? 2. Bài toán lập kế hoạch làm việc Dữ liệu : Cho n việc và một số nguyên k, mỗi việc được đặc trưng bởi bộ ba các số nguyên (ti, di, pi), với ti, di, và pi lần lượt biểu diễn thời gian thực hiện, thời gian kết thúc và hình phạt ứng với việc thứ i. 100 Lý thuyết tính toán Câu hỏi : Có thể sắp xếp các việc sao cho tổng số các hình phạt là nhỏ hơn hoặc bằng k ? Nói cách khác, với mọi hoán vị P của n số nguyên đầu tiên, ta kết hợp một số nguyên : Pp = p(j) j 1, n p (j) p(r) r 1, j P t d 0 = = ⎧ ⎡ ⎤= >⎣ ⎦⎪⎨⎪=⎩ ∑ ∑nãuú nãúu khäng và người ta tìm một hoán vị P nếu hoán vị P tồn tại sao cho Pp = k. 3. Bài toán sắp xếp trong các thùng chứa Dữ liệu : Cho số nguyên c (dung lượng của các thùng), n vật đặc trưng bởi các kích thước s1, s2, ..., sn với 0 < si ≤ c và một số nguyên k. Câu hỏi : Có thể đặt n vật vào nhiều nhất là k thùng chứa được không ? 4. Bài toán ba-lô (rucksack) Dữ liệu : Cho một số nguyên c (kích thước ba-lô) và n vật có các kích thước lần lượt s1, s2, ..., sn. Câu hỏi : Có thể bỏ đầy hoàn toàn ba-lô bởi một số vật lấy từ n vật đã cho ? 5. Bài toán thỏa mãn các biểu thức boolean ở dạng chuẩn hội Dữ liệu: Một biểu thức boolean ở dạng chuẩn hội. Câu hỏi : Có thể gán giá trị nào đó cho các biến làm biểu thức thỏa mãn ? 6. Bài toán đường đi Hamilton Dữ liệu: Một đồ thị G = . Câu hỏi : Tồn tại hay không một đường đi Hamilton (đi qua tất cả các đỉnh) trong đồ thị đã cho ? III.3. Ví dụ về rút gọn kiểu đa thức Bây giờ ta xét một ví dụ : hãy rút gọn kiểu đa thức bài toán ba-lô về bài toán sắp đặt các việc có hình phạt. Giả sử I = (s1, s2, ..., sn; c) là một dữ liệu vào cho bài toán ba-lô. - Nếu c n 1, j s j∑ = < thì câu trả lời là không. Khi đó, ta xét bài toán sắp đặt các việc có hình phạt được định nghĩa bởi ti = 2, di = pi = 1 và k = 0 với câu trả lời không. - Nếu trái lại, c n 1, j s j∑ = ≥ thì câu trả lời là thoả mãn. Ta xét bài toán sắp đặt các việc có hình phạt được định nghĩa bởi ti = pi = si và di = c với ∀i = 1 .. n, và k = c n 1, j s j∑ = − Bây giờ ta kiếm tra trường hợp cá biệt I của bài toán ba-lô có một lời giải nếu và chỉ nếu bài toán sắp đặt các việc có hình phạt mà ta sẽ đưa về cũng có một lời giải : Độ phức tạp tính toán 101 Nếu bài toán ba-lô có một lời giải, khi đó tồn tại một tập hợp con J thuộc khoảng { 1, ..., n } sao cho ∑j∈J sj = c. Ta chọn một hoán vị P sao cho tất cả các việc có chỉ số trong J được chọn trước các việc khác. Cả || J || việc này đều được làm xong trước ngày kết thúc của chúng, trong khi đó, các việc khác được làm xong sau ngày kết thúc, từ đó sinh ra một hình phạt: ∑J = || J|| + 1, npP (J) = ∑J = || J|| + 1, n sP (J) = ∑J = 1, n J ∈J = ∑J = 1, n sJ - c = k Như vậy, các việc được làm xong với một hình phạt nhỏ hơn hoặcbằng k, giả sử m là số nguyên lớn nhất sao cho m việc đầu tiên được làm xong trước ngày kết thúc chung của chúng là c. Như vậy, ta có: ∑J -- 1, m tP(J) ≤ c và hình phạt là : ∑J = m + 1, n PP(J) ≤ k Do ti = Pi = si, ta có ∑J - 1, m tP(J)z + ∑J - m + 1, n PP(J) = ∑J - 1,n sJ = c + k Do đó, cả hai bất đẳng thức đều bằng nhau và các vật có chỉ số P(j) với j = 1..m sẽ làm đầy ba-lô. Ta cần kiểm chứng rằng việc rút gọn là theo thời gian đa thức, nghĩa là chỉ có một phép tính duy nhất là tính giá trị ∑J - 1, n sJ - c. Rõ ràng phép tính này đòi hỏi một thời gian đa thức. Việc xây dựng bài toán sắp đặt các việc có hình phạt sẽ là có thời gian hằng nếu số nguyên này âm, có thời gian tuyến tính nếu số nguyên này dương. Cho đến lúc này, ta chưa biết có bài toán nào trong sáu bài toán trên thuộc vào lớp không P. Tuy nhiên, người ta dễ dàng chứng minh được rằng chúng đều thuộc lớp NP. Ví dụ 6. 2 Bài toán tô màu các đỉnh của một đồ thị là thuộc lớp NP. Thật vậy, máy Turing không đơn định sau đây nhận biết ngôn ngữ kết hợp với bài toán này về thời gian tuyến tính (và do vậy, là đa thức) : trong thời gian đầu, máy Turing thực hiện tô cho mỗi đỉnh, một cách không đơn định, một màu nào đó trong số k màu. Sau đó, máy Turing kiểm tra việc tô màu này đã thỏa mãn chưa, nghĩa là kiểm tra tại các mút của các cung xem các đỉnh có cùng một tô một màu không ?. Bây giờ ta chứng minh rằng thực tế tất cả sáu bài toán trên đều có thể rút gọn kiểu đa thức từ bài toán kia. Từ đó, cả sáu bài toán đều thuộc lớp P nếu và chỉ nếu một trong chúng thuộc P. Ta có định nghĩa sau đây : Định nghĩa 6.3 Một bài toán là NP-cứng (NP - Comlete) nếu nó ở trong lớp NP. Rõ ràng, định nghĩa trên có ích vì tồn tại những bài toán NP-đầy đủ như vậy. 102 Lý thuyết tính toán Định ký Cook - 1971 (Stephen Cook) : Bài toán về tính thỏa mãn của các biểu thức boolean dưới dạng chuẩn hội là một bài toán NP -đầy đủ. Ta không chứng minh định lý này. Bổ đề 6. 1 Cả sáu bài toán trên đây đều là NP-đầy đủ. Ta có mệnh đề sau: Mệnh đề 6. 4 P = NP nếu và chỉ nếu tồn tại ngôn ngữ L ∈ P sao cho L là NP-đầy đủ. Bài tập 1. Xét ngôn ngữ L = { wcw’ | w ∈ { a, b }* và w ≠ w’ } Chứng minh rằng L ∈ NTIME (n) ∩ DSPACE (log2 (n)). 2. Chứng minh rằng cả sáu bài toán đã nêu đều có thể rút gọn kiểu đa thức từ bài toán này về bài toán kia. 3. Một đồ thị được gọi là đầy đủ nếu có hai đỉnh bất kỳ được nối với nhau bới một cạnh. Đồ thị được gọi là k-đầy đủ nếu tồn tại một đồ thị con có k đỉnh là đầy đủ. Bài toán đầy đủ k-đầy đủ như sau: Dữ liệu : Một đồ thị G và một số nguyên k Câu hỏi : G có phải là k-đầy đủ? Chứng minh rằng bài toán đồ thị k-đầy đủ là bài toán NP đầy đủ. 4. Những bài toán sau đây thuộc lớp NP, thuộc lớp P, thuộc lớp NP-bộ nhớ ? Bài toán nào là NP-đầy đủ ? a) Dữ liệu : Một câu w biểu diễn một biểu thức Boolean. Câu hỏi : Câu w có phải là một hằng đúng (tautology) không ? b) Dữ liệu : Một máy Turing T trên bảng chữ { a, b }. Câu hỏi : Có tồn tại không một câu w ∈ S* có độ dài n sao cho máy Turing T nhận biết w hết một lượng thời gian nhỏ hơn boặc bằng n ? c) Dữ liệu : Một máy Turing trên bảng chữ { a, b }. Câu hỏi : Tồn tại hay không một câu có độ dài n sao cho T nhận biết câu này về bộ nhớ nhỏ hơn hoặc bằng n ? d) Dữ liệu : Một cặp đồ thị (G, G’). Câu hỏi : Đồ thị G’ có đẳng cấu (isomorphic) với một đồ thị con của G hay không ?
File đính kèm:
- giao_trinh_ly_thuyet_tinh_toan_phan_huy_khanh.pdf