Quy dẫn và NP-complete -- Reduction and NP-complete

Trong bài trước, chúng ta đã tìm hiểu hai lớp bài toán: PNP. Nói ngắn gọn, P là lớp bài toán quyết định mà chúng ta có thể giải trong thời gian đa thức còn NP là lớp bài toán mà chúng ta có thể kiểm tra lời giải trong thời gian đa thức. Về mặt trực quan, các bài toán dễ giải cũng là các bài toán dễ kiểm tra. Do đó, P $\subseteq $ NP. Câu hỏi P vs NP $$"Liệu các bài toán dễ kiểm tra lời giải thì có dễ giải hay không?" vẫn là một câu hỏi mở chưa có lời giải.

Trong bài này, chúng ta sẽ xem một cách tiếp cận đối với câu hỏi P vs NP thông qua một lớp các bài toán khó nhất trong số các bài toán trong lớp NP. Những bài toán đó được gọi là bài toán thuộc lớp NP-complete. Nhưng làm thế nào để biết được bài toán nào là khó nhất trong số vô hạn các bài toán trong NP? Cook và Levin độc lập đưa ra câu trả lời cho câu hỏi này, câu trả lời trở thành định lý Cook-Levin. Định lý này (cùng một số công trình khác) mang về cho Cook giải Turing. Công cụ sử dụng trong chứng minh của định lý Cook-Levin chính là quy dẫn (reduction). Phần đầu tiên của bài viết ta sẽ nghiên cứu công cụ này.

Remark: Trong lớp NP có cả những bài toán khó và dễ. Lớp các bài toán khó nhất là lớp NP-complete dưới đây.

Quy dẫn

Một input $x$ của một bài toán quyết định A được gọi là một Yes-instance nếu đầu ra tương ứng của input này là Yes. Ngược lại, ta gọi $x$ là một No-instance của bài toán A. Ta sẽ dùng $|x|$ để kí hiệu chiều dài của input $x$.

Karp Reduction: Một bài toán quyết định A gọi là quy được về (reducible to) bài toán quyết định B trong thời gian đa thức nếu với mỗi input $x$ của bài toán $A$, tồn tại một giải thuật $M$, trong thời gian $poly(|x|)$, tạo ra $M(x)$ sao cho $x$ là một Yes-instance của $A$ khi và chỉ khi $M(x)$ là một Yes-instance của bài toán B. Ta sẽ kí hiệu:

$A \preceq_{\mathrm{Karp}} B \qquad (1)$

 

Chữ Karp ở trên là tên của nhà khoa học Richard Karp, người đưa ra định nghĩa này.

Remarks: Quy dẫn có nhiều dạng khác nhau, nhưng ở đây ta chỉ xét quy dẫn Karp (Karp reduction) định nghĩa ở trên. Do đó, ta sẽ nói ngắn gọn là quy dẫn.

Tính bắc cầu của quy dẫn Karp: Nếu $A \preceq_{\mathrm{Karp}} B$ và $B \preceq_{\mathrm{Karp}} C $ thì $A \preceq_{\mathrm{Karp}} C$.

 
Chứng minh: Ta có nhận xét: nếu $p(x)$ là một đa thức bậc $a$, $q(x)$ là một đa thức bậc $b$ thì $p(q(x))$ là một đa thức bậc $a+b$. Một cách ngắn gọn, ta có:

$poly(poly(n)) = poly(n) \qquad (2)$

Gọi $x$ là một input của bài toán $A$. Gọi $M,N$ lần lượt là giải thuật quy dẫn từ $A$ sang $B$ và từ $B$ sang $C$. Gọi $MN = N \circ M$ là một giải thuật quy dẫn từ $A$ sang $C$, trong đó, với mỗi $x \in A$, ta thu được đầu ra $MN(x) = N(M(x)) \in C$. Theo định ngĩa, thời gian tính toán của thuật toán $MN$ là:

$poly(|M(x)|) + poly(|x|) $

Do $M$ là giải thuật có thời gian đa thức, ta có $|M(x)| = poly(|x|)$ (một giải thuật đa thức không thể có đầu ra có chiều dài lũy thừa). Theo $(2)$, ta có $poly(|M(x)|) = poly(|x|)$ (dpcm).


Lemma 1: Nếu $A \preceq_{\mathrm{Karp}} B$ và $B \in $P thì $A \in $ P.

 
Chứng minh: Gọi $x$ là một đầu vào của bài toán $A$. Để xác định xem $x$ có phải là một Yes-instance của $A$ hay không, ta sẽ:

  1. Áp dụng thuật toán quy dẫn $M$ để biến đầu vào $x$ thành đầu vào $M(x)$ của bài toán $B$. Do thuật toán quy dẫn có thời gian đa thức, chiều dài của $|M(x)|$ cũng là đa thưc, i.e, $|M(x)| = poly(|x|)$.
  2. Xác định xem $M(x)$ có phải là một Yes-instance của $B$ hay không. Việc xác định này có thể thực hiện được trong thời gian $poly(|M(x)|)$ vì $B \in $P.

Theo $(2)$, $poly(|M(x)|) = poly(poly(|x|)) = poly(|x|)$, cả hai bước trên đều có thể thực hiện được trong thời gian đa thức (dpcm).


Ý nghĩa của quy dẫn: Quy dẫn cung cấp cho chúng ta một công cụ rất đẹp để định lượng "độ khó" giữa hai bài toán. Nếu $A \preceq_{\mathrm{Karp}} B$, Lemma 1 cho chúng ta biết bài toán $A$ sẽ dễ hơn bài toán $B$, theo nghĩa, nếu ta giải được $B$ trong thời gian đa thức thì ta cũng giải được $A$ trong thời gian đa thức. Điều ngược lại có thể sẽ không đúng. Sau đây ta xét ví dụ minh họa quy dẫn giữa hai bài toán DominoTilingBipartitePerfectMatching.

DominoTiling. Cho một bàn cờ ô vuông kích thước $n\times n$, trong đó một số ô của bàn cờ đã bị xóa. Có tồn tại hay không một cách xếp các quân Domino sao cho không có 2 quân Domino nào chồng lên nhau và các quân Domino phủ kín bàn cờ?

 
Ví dụ:
domino-tiling
Figure 1: (a) Một bàn cờ $4\times 4$ và một số ô bị xóa (các ô bị tô màu đen) và (b) một cách xếp các quân domino phủ kín bàn cờ.

BipartitePerfectMatching. Cho một đồ thị đơn hai phía (bipartite graph) và vô hướng $G(A\cup B,E)$. Một cặp ghép (matching) là một tập cạnh $M \subseteq E$ sao cho không có hai cạnh nào có chung một đầu mút. Một cặp ghép được gọi là hoàn hảo (perfect matching) nếu $|M| = |A| = |B|$, i.e, mọi đỉnh của đồ thị đều nằm trong cặp ghép. Có tồn tại hay không một cặp ghép hoàn hảo trong $G(V,E)$?

 
Ví dụ:
perfect-matching
Figure 2: Đồ thị hai phía với các đỉnh tô màu xám ở một phía và các đỉnh màu trắng ở phía còn lại. Các cạnh tô đậm màu đỏ là một cặp ghép hoàn hảo. Đồ thị này được xây dựng từ thuật toán quy dẫn trình bày dưới đây áp dụng cho Figure 1(a).

Ta có:

Lemma 2:

DominoTiling $ \preceq_{\mathrm{Karp}}$ BipartitePerfectMatching

 
Chứng minh: Từ bàn cờ kích thước $n \times n$, ta tạo ra một đồ thị $G(V,E)$ trong đó mỗi đỉnh của đồ thị là một ô (chưa bị xóa) của bàn cờ và mỗi cạnh nối hai đỉnh tương ứng với hai ô kề nhau của bàn cờ (hai ô vuông có chung một cạnh). Đồ thị $G(V,E)$ là đồ thị hai phía vì ta có thể lấy các đỉnh tương ứng với các ô đen của bàn cờ là một phía và các đỉnh tương ứng với các ô trắng là phía còn lại.

Ta chỉ cần chứng minh bàn cờ có thể phủ được bằng các quân Domino khi và chỉ khi đồ thị $G(V,E)$ có cặp ghép hoàn hảo. Thật vậy, nếu bàn cờ có thể phủ kín được bằng cách quân Domino, mỗi quan Domino sẽ tương ứng với một cạnh của cặp ghép. Do đó, $G(V,E)$ có một cặp ghép hoàn hảo. Ngược lại, với mỗi cạnh của cặp ghép hoàn hảo của $G(V,E)$, ta đặt một quân Domino phủ hai đỉnh tương ứng của cạnh đó. Do cặp ghép là hoàn hảo, các quân Domino sẽ phủ kín bàn cờ (dpcm).


Bài toán tìm cặp ghép hoàn hảo của đồ thị hai phía có thể giải được trong thời gian đa thức, ta suy ra BipartitePerfectMatching $\in$ P. Do đó, theo Lemma 1, DominoTiling $\in$ P.

NP-complete

Ta đã có trong tay công cụ để xác định độ khó giữa các bài toán. Giờ ta có thể định nghĩa một lớp các bài toán "khó", khó hơn tất cả các bài toán trong lớp NP.

NP-hard: Một bài toán quyết định $B$ được gọi là thuộc lớp bài toán NP-hard nếu với mọi bài toán $A \in$ NP, ta có:

$A \preceq_{\mathrm{Karp}} B $

 

Nếu bài toán $B$ trong định nghĩa trên cũng thuộc lớp NP, ta nói $B$ thuộc lớp NP-complete.

NP-complete = NP $\cap $ NP-hard $\qquad (3)$

 

Nhắc lại: một bài toán quyết định được gọi là thuộc lớp NP nếu bài toán đó có một bằng chứng đơn giản dễ kiểm tra.

Theo định nghĩa trên, NP-complete chỉ là một lớp bài toán con của lớp NP-hard. Lớp NP-hard còn bao gồm những bài toán mà kể cả cho máy tính vô hạn thời gian, nó cũng không giải được. Ngược lại, tất cả các bài toán thuộc lớp NP ta đều có thể giải được trong một thời gian hữu hạn; cụ thể là thời gian lũy thừa.

Cũng theo định nghĩa trên, một bài toán thuộc NP-complete thì cũng thuộc NP-hard. Do đó, nó là một bài toán "khó nhất" trong số các bài toán trong lớp NP. Nếu ta có thể giải được một bài toán nào đó trong lớp NP-complete trong thời gian đa thức thì ta có thể giải được tất cả các bài toán trong lớp NP trong thời gian đa thức.

Lớp bài toán NP-complete theo định nghĩa ở trên thực sự là một lớp bài toán thú vị. Tuy nhiên, liệu một bài toán NP-complete có tồn tại hay không? Nếu tồn tại thì nó trông như thế nào? Cook và Levin chứng minh rằng không những tồn tại một bài toán NP-complete mà còn tồn tại một bài toán NP-complete rất "đẹp".

Cook-Levin Theorem: Sat $\in$ NP-complete.

 

Định nghĩa bài toán Sat, bạn đọc có thể xem tại post trước. Chứng minh định lý Cook-Levin vượt quá khuôn khổ của bài viết. Bạn đọc có thể xem tại CLRS Chapter 36 [2]. Nếu nghĩ sâu hơn về định lính này, thực sự đây là một kết quả ngạc nhiên. Tất cả các bài toán NP đều "dễ" hơn Sat.

Remark: Bài toán thực sự mà Cook-Levin chứng minh thuộc NP-complete là CircuitSat, một phiên bản dạng mạch điện tử của Sat. Richard Karp chính là người chứng minh Sat mà ta định nghĩa ở blog này thuộc NP-complete. Do không muốn đi "đường vòng" qua CircuitSat nên mình cho Sat vào định lí Cook-Levin.

Sau định lý Cook-Levin, Richard Karp [3] chứng minh 21 bài toán khác cũng thuộc lớp NP-complete. Một vài trong số đó là các bài toán NP mà ta đã định nghĩa ở post trước. Trong post tới đây, ta sẽ chứng minh một số bài toán đó là NP-complete. Các chứng minh của Karp đều dựa trên bổ đề sau:

Lemma 3: Nếu $A$ là một bài toán NP-complete và $B$ là một bài toán NP thỏa mãn $A \preceq_{\mathrm{Karp}} B $ thì $B$ là một bài toán NP-complete.

 
Chứng minh: Gọi $C$ là một bài toán trong NP. Vì $A \in $NP-complete, ta có $C \preceq_{\mathrm{Karp}} A$. Do $A \preceq_{\mathrm{Karp}} B$, theo tính bắc cầu của quy dẫn, ta suy ra $C \preceq_{\mathrm{Karp}} B$. Như vậy, mọi bài toán trong NP đều có thể quy về $B$, do đó, $B \in $NP-hard. Do $B \in $NP, ta suy ra dpcm.


Sau đây ta sẽ chứng minh 3Sat thuộc NP-complete để minh họa ý tưởng. Bài toán 3Sat là bài toán Sat trong đó mỗi mệnh đề chỉ có tối đa 3 literals (xem định nghĩa đầy đủ tại post trước).

Theorem 2: 3Sat $\in$ NP-complete.

 
Chứng minh: Theo Lemma 3 và Cook-Levin theorem, ta chỉ cần chứng minh

Sat $ \preceq_{\mathrm{Karp}}$ 3Sat

Gọi $\varphi(n,m)$ là một input Sat. Ta sẽ tìm cách biến đổi, trong thời gian $poly(n+m)$, $\varphi(n,m)$ thành một biểu thức $\varphi'(n',m')$ sao cho $\varphi'(n',m') \in $ 3Sat và $\varphi(n,m)$ thỏa mãn được (satisfiable) khi và chỉ khi $\varphi'(n',m')$ thỏa mãn được.

Lấy một mệnh đề $C$ trong $\varphi(n,m)$ mà mệnh đề này có $k$ biến với $k \geq 4$. Các biểu thức 3 biến ta chỉ cần giữ nguyên. Không mất tính tổng quát, giả sử $C = (x_1 \vee \bar{x}_2 \vee \bar{x}_3 \vee x_4 \vee \ldots \vee x_k)$. Chú ý, ở đây dấu phủ trên hai biến $x_2$ và $x_3$ không đóng vai trò gì đặc biệt. Thêm một biến $z$ (không xuất hiện trong $\varphi(n,m)$) và thay $C$ bằng hai mệnh đề mới:

$(x_1 \vee \bar{x}_2 \vee z) \wedge (\bar{z} \vee \bar{x}_3 \vee x_4 \vee \ldots \vee x_k)$

và gọi $\varphi_1(n_1,m_1)$ là biểu thức thu được. Ta thấy:

  1. $n_1 = n +1$ và $m_1 = m+1$.
  2. $\varphi_1(n_1,m_1)$ có thêm đúng 1 biểu thức có 3 biến và một biểu thức có $k-1$ biến.
  3. $\varphi(n,m)$ thỏa mãn được (satisfiable) khi và chỉ khi $\varphi_1(n_1,m_1)$ thỏa mãn được. Chứng minh tính chất này không khó và coi như bài tập cho bạn đọc.
  4. Biến đổi $\varphi(n,m)$ thành và $\varphi_1(n_1,m_1)$ có thể thực hiện được trong thời gian đa thức.

Để thu được biểu thức 3Sat, ta chỉ cần áp dụng phép biến đổi trên nhiều lần đối với mọi mệnh đề có ít nhất 4 biến cho đến khi nào ta thu được biểu thức mà các mệnh đề chỉ có không quá 3 biến. Số lần áp dụng phép biến đổi trên tối đa là $mn$, do đó, tổng thời gian của các phép biến đổi là $mn \times poly(n+m) = poly(n+m)$. Theo tính chât 3, biểu thức cuối cùng thỏa mãn được khi và chỉ khi biểu thức ban đầu thỏa mãn được (dpcm).


Tham khảo

[1] S. A. Cook. The Complexity of Theorem-proving Procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151-158. ACM, 1971.
[2] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms (2nd ed.). Chapter 36. MIT Press and McGraw-Hill. ISBN 0-262-03293-7. (2001).
[3] R. M. Karp. Reducibility among Combinatorial Problems. Complexity of Computer Computations. Springer US, 1972. 85-103.

Facebook Comments

Tags: , , , , , , , ,

Reply

Your email address will not be published. Required fields are marked *