- Blog Khoa Học Máy Tính - -

PCP 4 — Gap-preserving reduction và bài toán LabelCover

7.d. Vài ví dụ về gap-preserving reduction

Những reduction tầm thường như kiểu từ Gap-Max-Clique(c,s) về Gap-Max-IndependentSet(c,s) sẽ có tính chất gap-preserving một cách hiển nhiên. Chúng ta xét vài ví dụ không tầm thường: Gap-Max-3SAT(d), Gap-Max-E3SAT(Ed) và Gap-Max-LabelCover; sau này sẽ dùng chúng để chứng minh định lý Hastad và làm động cơ giới thiệu Unique Games Conjecture.

Định nghĩa: bài toán Max-3SAT(d). Input của bài toán này là một công thức CNF \varphi sao cho mỗi clause có nhiều nhất là 3 biến, và mỗi biến xuất hiện trong nhiều nhất là d clauses. (Một biến x_i có thể xuất hiện như x_i hoặc \bar x_i.)

Chúng ta sẽ dùng một gap-preserving reduction từ Gap-Max-E3SAT(1,\rho) (đã biết là NP-hard từ Bài 2) về Gap-Max-3SAT(d)(1,\eta) để chứng minh rẳng Gap-Max-3SAT(d)(1,\eta) là NP-hard với các hằng số có thể thỏa mãn được, thì toàn bộ các clauses của \psi cũng thỏa mãn được.

(b) Nếu một truth assignment bất kỳ chỉ có thể thỏa mãn được tối đa một tỉ lệ \rho của tổng số clauses của \varphi, thì một truth assignment bất kỳ cũng chỉ có thể thỏa mãn được tối đa là tỉ lệ \eta của tổng số clauses của \psi.

Để mô tả reduction này, chúng ta cần một khái niệm cực kỳ quan trọng là expander graphs. Sẽ nói kỹ hơn nhiều về expander graphs trong bài tới, cho nên ở đây chỉ định nghĩa một trường hợp đặc biệt của expanders. Kỹ thuật dùng expanders trong reductions là một kỹ thuật then chốt trong các chứng Hardness of approximation. Chúng ta sẽ dùng expanders theo vài cách khác nhau. Đôi khi dùng theo cách “tổ hợp” như trong ví đụ đang xét. Đôi khi dùng theo cách xác suất để “trộn” thông tin hoặc khuếch đại gap.

Một trường hợp đặc biệt của expanders. Một đồ thị G được gọi là một \alpha-edge expander nếu, với mọi tập con S\subset V(G) của các đỉnh với |S| \leq |V|/2, ta đều có |[S,V-S]| \geq \alpha |S|. Trong đó, [S,V-S] ký hiệu tập tất cả các cạnh của G đi từ S sang V-S. (Còn gọi là cái cut [S,V-S].) Chú ý rằng đồ thị này có thể có multi-edges (nhiều cạnh giữa cùng một cặp đỉnh).

Chúng ta biết rằng, tồn tại một hằng số d (cỡ khoảng 14), sao cho, với mọi n \geq 2 ta có thể xây dựng một 1-edge expander với n đỉnh và regular degree d trong thời gian poly(n). Thêm cạnh thì chỉ làm expander “tốt” hơn, do đó nếu có expanders với d=d_0 thì có expander với d \geq d_0. (Đây là trực quan. Sẽ chứng minh trong bài sau.)

Giả sử instance \varphi của Gap-Max-E3SAT có n biến x_1,\dots, x_nm clauses là C_1,\dots, C_m. Giả sử biến x_i xuất hiện f_i lần. Chú ý rằng \sum_i f_i = 3m. Tạo một biến y_{i,j} nếu biến x_i xuất hiện trong clause C_j. Như vậy, có tổng cộng 3m biến y_{i,j} này. Chúng sẽ là các biến của công thức \psi đang cần xây dựng. Có hai loại clauses cho \psi: clause cơ bản, và clause nhất quán, xây dựng như sau.

Bài tập: chứng minh rằng \psi có tổng cộng 3m biến và (3d+1)m clauses. Mỗi clause có nhiều nhất 3 biến, và mỗi biến xuất hiện ở nhiều nhất là 2d+1 clauses. Nói cách khác, \psi là một instance của Gap-Max-3SAT(2d+1).

Chứng minh (a) rất dễ: gán cho tất cả y_{i,j} cùng giá trị với x_i là xong.

Để chứng minh (b), giả sử có nhiều hơn \eta(3d+1)m clauses của \psi được thỏa mãn bởi một truth assignment t nào đó. (Giả trị cụ thể của \eta sẽ được xác định sau.) Chúng ta sẽ suy ra điều nghịch lý là nhiều hơn \rho m clauses của \varphi cũng được thỏa mãn bởi một truth assignment nào đó.

Xét một truth assignment t' cho \psi xây dựng như sau: với mỗi i cố định, gán cho tất cả các y_{i,j} giá trị TRUE hay FALSE mà phần lớn các y_{i,j} nhận được từ t. (Nghĩ: có tất cả f_i phiếu “bầu” cho TRUE/FALSE. Cả đám lấy giá trị của số đông.) Nếu có “hòa” thì gán TRUE/FALSE tùy hỉ. Ta khẳng định rằng t' thỏa mãn số clauses ít nhất bằng với t thỏa mãn. Tại vì: sau khi chuyển giá trị một (thiểu) số s các y_{i,j} thì có thể một số clause cơ bản đang từ thỏa mãn biến thành không thỏa mãn. Sẽ có nhiều nhất là s clause cơ bản bị chuyển. Định nghĩa S là tập các đỉnh [i,j] của G_iy_{i,j} là thiểu số. Thì, |S| = s \leq |V(G_i)|/2. Do đó, theo định nghĩa của 1-edge expander, có ít nhất |S|=s cạnh của G_i nối S sang V(G_i)-S. Mỗi cạnh như vậy tương ứng với 2 clause nhất quán. Với mỗi cặp clause nhất quán này, chỉ có một là thỏa mãn bởi t, nhưng cả hai đều được thỏa mãn bởi t'. Vì thế, chúng ta “mất” sự thỏa mãn của \leq s clause cơ bản, nhưng lại kiếm “lời” được \geq s clause nhất quán. Vì thế, tổng số clauses thỏa mãn bởi t' ít nhất là bằng tổng số clause thỏa mãn bởi t.

Từ truth assignment t' dễ dàng tìm được truth assignment cho \varphi bằng các gán cho x_i cái giá trị mà tất cả các y_{i,j} được gán. Rõ ràng là truth assignment này thỏa mãn nhiều hơn \eta(3d+1)m - 3dm clauses của \varphi. Do đó, chỉ cần chọn \eta sao cho \eta(3d+1)-3d \geq \rho là xong chứng minh. Ta chọn luôn \eta = \frac{3d+\rho}{3d+1}. Chúng ta vừa chứng minh xong định lý sau đây.

Định lý. Với mọi hằng số d \geq 29, tồn tại một hằng số 0<\eta<1 sao cho Gap-Max-3SAT(d)(1,\eta) là NP-hard. (Chú ý: có thể giảm d xuống còn \geq 5. Đọc bài của Feige.)

Bài tập: Đôi khi, trong một số ứng dụng, chúng ta cần Gap-Max-E3SAT(Ed): giống như Gap-Max-3SAT(d) nhưng mỗi biến xuất hiện chính xác d lần, và mỗi clause chứa đúng 3 biến. Tìm một gap-preserving reduction từ Gap-Max-3SAT(d)(1,\eta) về Gap-Max-E3SAT(Ed)(1,\rho) để chứng minh rằng Gap-Max-E3SAT(Ed)(1,\rho) là NP-hard với một hằng số 1>\rho>0 nào đó.

7.e. Bài toán LabelCover_\Sigma

Định nghĩa. Một instance của bài toán Max-LabelCover_\Sigma bao gồm một bipartite graph G=(U,W; E), một alphabet \Sigma, và một hàm số h_{uw}: \Sigma \to \Sigma cho mỗi cạnh uw \in E. Một phép gán nhãn L: U\cup W \to \Sigma sẽ gán một nhãn trong tập \Sigma cho mỗi đỉnh của đồ thị. Phép gán nhãn này thỏa mãn cạnh uw nếu L(u) = h_{uw}(L(w)). Mục tiêu là thỏa mãn càng nhiều cạnh càng tốt.

Gọi \mathsf{opt}(G) là tỉ lệ các cạnh thỏa mãn được bởi phép gán nhãn tối ưu. Trong bài toán Gap-Max-LabelCover_\Sigma(c,s) thì một input instance G hoặc là thỏa \mathsf{opt}(G) \geq c hoặc là \mathsf{opt}(G) \leq s. Chúng ta phải quyết định xem cái nào là cái nào.

Định lý. Tồn tại một hằng số 0<\eta<1 sao cho Gap-Max-LabelCover_\Sigma(1,\eta) là NP-hard; trong đó |\Sigma|=7. Hơn nữa, chúng ta có thể giả sử thêm rằng mỗi bipartite graph instance của bài toán này là left-regular và right-regular với constant left-degree và constant right-degree.

Chứng minh. Ta xây dựng một gap-preserving reduction từ Gap-Max-E3SAT(Ed)(1,\rho) về Gap-Max-LabelCover_\Sigma(1,\eta) như sau. Xét một instance \varphi của Gap-Max-E3SAT(Ed)(1,\rho) với tập biến X và tập clauses \mathcal C = \{C_1,\dots,C_m\}. Xây dựng một bipartite graph G=(U,W;E) trong đó U = X là tập các biến, và W = \mathcal C là tập các clauses. Có một cạnh của E nối biến x_i với clause C_j nếu và chỉ nếu x_i xuất hiện trọng C_j. Định nghĩa \Sigma = \{001,010, 100, 011,101,110,111\} (có tất cả 7 symbols). Nghĩ về symbol 001 như đại diện cho FALSE, và symbol 111 đại diện cho TRUE.

Để cụ thể, giả sử C_j = x_a \vee \bar x_b \vee x_c. Chúng ta định nghĩa các hàm h_{aj}, h_{bj}, h_{cj} như sau. Đại khái, chúng đại diện cho trực quan là cái nhãn gán cho C_j phải là một nhãn từ \Sigma — đại diện cho một trong 7 cách làm C_j được thỏa mãn. Hàm số h_{aj} sẽ chỉ định giá trị nào của x_a tương ứng với nhãn của C_j. Ví dụ: h_{aj}(001) = FALSE = 001, h_{aj}(010) = FALSE = 001, h_{aj}(100) = TRUE = 111, h_{aj}(011) = FALSE = 001, h_{aj}(101) = TRUE = 111, h_{aj}(110) = TRUE = 111, và h_{aj}(111) = TRUE = 111. Trong khi đó, h_{bj}(001) = TRUE = 111 tại vì \bar x_b xuất hiện trong C_j chứ không phải x_b.

Chiều thuận: giả sử tồn tại một truth assignment thỏa mãn toàn bộ các clauses của \varphi, thì dễ thấy là tất cả các cạnh của G cũng thỏa mãn được.

Chiều nghịch: giả sử là > \eta 3m các cạnh của G được thoả mãn bởi một phép gán nhãn nào đó. Chúng ta sẽ chứng minh rằng tồn tại một truth assignment thỏa mãn > \rho m các clauses của \varphi. (Giá trị của \eta xác định sau.) Đơn giản thôi. Xét cái truth assignment tương ứng với các nhãn của U = X. Xét một clause C_j bất kỳ. Nếu cả 3 cạnh nối với C_j đều được thỏa mãn thì clause C_j dĩ nhiên là được thỏa mãn bởi truth assignment này. Do có > \eta 3m các cạnh của G được thoả mãn, tổng số clauses với cả 3 cạnh kề thỏa mãn sẽ lớn hơn (3\eta - 2)m clauses. (Bài tập: tại sao?) Ta chỉ cần chọn \eta sao cho (3\eta -2) \geq \rho là xong. Chọn \eta = \frac{\rho+2}{3} là được.

Cuối cùng: dĩ nhiên là bipartite graph ta xây dựng ở trên có left-degree là d và right-degree là 3.

QED