Trong bài viết này, chúng ta sẽ tìm hiểu một số bài toán NP-complete khi mà đầu vào là các số nguyên lớn. Ta gọi các bài toán NP-complete kiểu này là các bài toán Weakly NP-complete Problems. Bài toán đầu tiên là bài toán SubsetSum.

Trong bài quy hoạch động, chúng ta đã tìm hiểu thuật toán giải bài toán SubsetSum với thời gian $O(nT)$. Thoạt nhìn, thuật toán này có vẻ như có thời gian đa thức, vì ta không thấy lũy thừa ở đâu cả. Tuy nhiên, đây lại chính là thuật toán với thời gian lũy thừa. Tại sao vậy? Nhắc lại, ta luôn đo độ phức tạp (thời gian) là một hàm của chiều dài của input. Số nguyên $T$ có thể được biểu diễn bằng $O(\log T)$ bít, do đó, nó có chiều dài $\ell = O(\log T)$. Như vậy, thời gian $O(nT) = O(n 2^{\log T}) = O(n2^\ell)$ chính là một hàm lũy thừa. Các bạn có thể xem lại cách ta định nghĩa độ phức tạp của thuật toán. Trong bài này, ta sẽ chứng minh, khi $T$ rất lớn, bài toán SubsetSum là một bài toán NP-complete.

Hai bài toán khác chúng ta cũng xét trong phần này là bài toán Knapsack và bài toán Partition. Bài toán Partition, về mặt ứng dụng, ít được biết đến hơn bài toán Knapsack. Tuy nhiên, nó lại được dùng nhiều trong chứng minh tính NP-complete của rất nhiều bài toán khác.

Ta sẽ lần lượt chứng minh các bài toán trên là NP-complete dựa trên sơ đồ quy dẫn sau.

Bài toán VertexCover là bài toán NP-complete mà ta đã chứng minh ở post trước. Mình nhắc lại bài toán đó ở đây.

 
Chứng minh: Ta sẽ quy dẫn từ bài toán VertexCover như sau. Gọi $n,m$ lần lượt là số đỉnh của đồ thị. Ta thực hiện hai bước sau:

1. Đánh số các cạnh của đồ thị từ $0$ tới $m-1$. Cạnh thứ $i$ ta gán cho nó trọng số $X[e_i] = 10^i$ và gán cho hai đỉnh đầu mút của nó, mỗi đỉnh một trọng số $10^i$.
2. Với mỗi đỉnh $v$ của đồ thị, ngoài trọng số nó nhận được từ các cạnh kề với nó từ bước 1, ta cộng thêm cho nó một trọng số $10^m$. Gọi $X[v]$ là tổng trọng số cuối cùng của đỉnh $v$.

Gọi $E_v$ là tập các cạnh kề với đỉnh $v$. Ta có nhận xét về tổng trọng số mà đỉnh $v$ nhận được sau hai bước trên là:

$X[v] = 10^m + \sum_{j \in E_v} 10^{j} \qquad (1)$

Nếu viết $X[v]$ trong cơ số $10$, ta có thể hiểu đại lượng $X[v]$ như sau: chữ số thứ $m+1$ của $X[v]$ luôn là 1 và chữ số thứ $j$ của $X[v]$ là $1$ khi và chỉ khi $v$ kề với cạnh $j+1$

Mảng $X$ của chúng ta bao gồm tất cả các đỉnh và cạnh, có kích thước $m+n$. Cạnh $i$, $0 \leq i \leq m-1$, có giá trị $10^i$, và đỉnh $v$, $1 \leq v\leq n$ có giá trị như trong phương trình $(1)$. Ta thiết lập:

$T = K\cdot 10^m + 2*\sum_{i=0}^{m-1} 10^i \qquad (2)$

Ta sẽ chứng minh $G(V,E)$ có một tập phủ đỉnh kích thước $K$ khi và chỉ khi $X$ có một tập con có tổng giá trị $T$ định nghĩa trong $(2)$.

Chiều thuận: Gọi $A$ là tập phủ đỉnh của đồ thị với kích thước $K$. Ta xây dựng tập con $S$ của $X$ bao gồm: (i) tất cả các đỉnh trong $A$ và (2) các cạnh của đồ thị có đúng một đầu mút trong $A$. Do $A$ là một tập phủ đỉnh, mỗi cạnh có ít nhất một đầu mút trong $A$. Việc kiểm tra xem các phần tử trong $S$ có tổng giá trị $T$ coi như bài tập cho bạn đọc.

Chiều ngược: Gọi $S$ là một tập con của $X$ có tổng giá trị $T$. Do tổng trọng số các cạnh của đồ thị là $\sum_{i=0}^{m-1} 10^i $, nhỏ hơn $10^m$, tập $S$ gồm đúng $K$ đỉnh (và có thể có thêm một số cạnh). Gọi $A$ là tập các đỉnh trong $S$. Ta chỉ còn phải chứng minh mọi cạnh đều có ít nhất một dầu mút trong $A$. Giả sử có một cạnh, ví dụ cạnh có số thứ tự $\ell$ với $0 \leq \ell \leq m$, không có đầu mút nào trong $A$. Cạnh này có trọng số $10^\ell$. Do đó, cạnh nà đóng góp $10^\ell$ vào $T$. Tuy nhiên, do cạnh này không kề với đầu mút nào trong $A$ và $2*\sum_{i = 0}^{\ell-1}10^i$ nhỏ hơn $10^\ell$, $T$ chỉ chứa tối đa $10^\ell$, trái với định nghĩa trong $(2)$ là $T$ chứa $2*10^\ell$.

Nhận thấy, bài toán Partition thực ra là một trường hợp đặc biệt của bài toán SubsetSum khi $X[i] = Y[i]$ và $T = \frac{\sum_{i=1}^n Y[i]}{2}$. Do đó, một cách chứng minh "đơn giản" Theorem 2 từ Theorem 1 là cho $T = \frac{\sum_{i=1}^n Y[i]}{2}$. Cách chứng minh này thực ra là một cách chứng minh sai. Lý do tại sao coi như bài tập cho bạn đọc (xem lại định nghĩa quy dẫn).

Chứng minh Theorem 2: Ta đặt $C = \sum_{i=1}^n X[i]$. Gọi $Y$ là tập gồm $n+2$ phần tử, trong đó $Y[i] = X[i]$ với mọi $1 \leq i\leq n$ và $Y[n+1] = C^2 + T$, $Y[n+2] = C^2 + C - T$. Ta sẽ chứng minh tập $X$ có một tập con có tổng giá trị $T$ khi và chỉ khi tập $Y$ có thể được chia thành hai tập con có tổng giá trị bằng nhau. Chứng minh chi tiết coi như bài tập cho bạn đọc, dựa trên nhận xét rằng $Y[n+1]$ và $Y[n+2]$ không thể cùng thuộc một tập con.

 
Chứng minh: Ta quy dẫn từ bài toán SubsetSum bằng cách cho $v_i = w_i = X[i]$ và $V = W = T$. Chi tiết còn lại chỉ mang tính thủ tục và mình coi như bài tập cho bạn đọc.

Tham khảo

[1] J. Erickson. Lecture Notes on NP-hardness. UIUC. 2014
[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] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of Np-Completeness. W. H. Freeman & Co., New York, NY, USA. 1979.