Một số bài toán NP-complete với đầu vào là số nguyên lớn -- Weakly NP-complete problems

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.

SubsetSum Cho một mảng n phần tử X[1,2,\ldots, n], trong đó phần tử thứ i có giá trị X[i], và một số T. Có tồn tại hay không một tập con các phần tử của mảng X sao cho tổng giá trị của chúng bằng T.

 

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.

Partition: Cho một mảng n phần tử Y[1,2,\ldots, n], trong đó phần tử thứ i có giá trị Y[i]. Có tồn tại hay không một cách chia tập X làm đôi sao cho tổng giá trị của hai tập con bằng nhau.

 

Knapsack: Cho n đồ vật, trong đó đồ vật thứ i có trọng lượng w_i và giá trị v_i và một cái ba lô có khả năng mang được trọng lượng tối đa W. Liệu ta có thể đựng được đồ vật trong ba lô (mà không quá giới hạn trọng lượng của ba lô) có tổng giá trị ít nhất V hay không?

 

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.
weak-reduction
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.

VertexCover Cho một đồ thị vô hướng G(V,E) và một số nguyên K. Có tồn tại hay không một tập phủ đỉnh có kích thước không quá K trong đồ thị? Một tập đỉnh A\subseteq V được gọi là một tập phủ đỉnh (vertex cover) nếu như với mọi cạnh e của đồ thị, ít nhất một trong hai đầu mút của nó thuộc A.

 

Theorem 1: SubsetSum \in NP-complete

 
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]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 A2*\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)T chứa 2*10^\ell.


Theorem 2: Partition \in NP-complete

 

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]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 nY[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]Y[n+2] không thể cùng thuộc một tập con.


Theorem 3: Knapsack \in NP-complete

 
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 = 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.

Tags: , , , , ,

Reply

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