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

NQH | 19/05/2009 |

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ố $0<\eta<1, 0<d$ nào đó. Reduction này chuyển một instance $\varphi$ của Gap-Max-E3SAT $(1, \rho)$ về một instance $\psi$ của Gap-Max-3SAT(d) $(1, \eta)$ sao cho:

(a) Nếu toàn bộ các clauses của $\varphi$ 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_n$ và $m$ 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.

$m$ clause cơ bản: với mỗi clause $C_j = x_a \vee x_b \vee x_c$ ( $1 \leq j \leq m$ ), tạo một clause cơ bản $y_{a,j} \vee y_{b, j} \vee y_{c, j}$ cho $\psi$ . Nếu $C_j$ chứa phần bù của một biến thì clause cơ bản cũng chứa phần bù của biến $y$ tương ứng. Nói cách khác, chúng ta “tách” sự xuất hiện của mỗi biến $x_i$ thành $f_i$ biến độc lập dạng $y_{i,j}$ .
các clause nhất quán. Kế đến, vì các biến $y_{i,j}$ độc lập với nhau, cần một cách nào đó để ràng buộc cho chúng nó “tương ứng” với một giá trị TRUE/FALSE của biến $x_i$ . Chúng ta làm như sau. Xây dựng một $d$ -regular $1$ -edge expander $G_i$ với $f_i$ đỉnh. Như ở trên đã nói, đồ thị này có thể xây dựng được trong poly-time. Đánh nhãn các đỉnh của $G_i$ bằng $[i,1], \dots, [i,f_i]$ . Với mỗi cạnh $([i, j,], [i,j']) \in E(G_i)$ , thêm hai “clause nhất quán” $y_{i,j} \vee \overline y_{i,j'}$ và $\overline y_{i,j} \vee y_{i,j'}$ vào $\psi$ . Lý do chúng ta thêm chúng vào là vì: nếu giá trị của $y_{i,j}$ khác với $y_{i,j'}$ thì ít nhất một trong hai clause nhất quán này sẽ không được thỏa mãn; còn nếu $y_{i,j}$ và $y_{i,j'}$ nhất quán với nhau thì cả hai clauses sẽ được thỏa mãn.

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_i$ mà $y_{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

Chủ đề : Lý thuyết tính toán, Thuật Toán. Bookmark the permalink. Trackbacks are closed, but you can post a comment.

10 Comments

Thinh Nguyen

Posted 19/05/2009 at 10:48 pm | Permalink

Bài tập 1: $\psi$ có 3m biến vì $\sum_i f_i = 3m$ . Số lượng clauses cũng đếm được dễ dàng: $(3d + 1)m = 3dm + m$ , ta có m clauses cơ bản và $(3m)d$ clauses nhất quán (đặt các $G_i$ cạnh nhau thu được $G$ là d-regular với 3m đỉnh)

Mỗi clause có nhiều nhất 3 biến.
Mỗi biến $y_{i,j}$ xuất hiện trong nhiều nhất là 1 clause cơ bản, và tương ứng với $d$ cạnh adjacent với nó là $2d$ clauses nhất quán nên nó xuất hiện ở nhiều nhất $2d+1$ clauses.

Bài tập 2: (chờ comment sau)

(Thử Latex plugin là chính)

Cái expander này chắc phải học cả một textbook về nó thì mới hiểu được cặn kẽ. Em thấy là ta đang bước vào đoạn đường khó khăn đầu tiên của “Phi lộ” đề ra trong bài post PCP1.

Reply
Thinh Nguyen

Posted 20/05/2009 at 9:32 am | Permalink

Trước hết, em thấy chuỗi bài PCP rất trực quan sinh động, giúp readers từng bước phác hoạ được bức tranh PCP theory ở thời kỳ đầu. Đây là một ưu điểm chính của chuỗi bài này. Lẽ dĩ nhiên khi ta đã trung thành với phương châm “trực quan sinh động” trong cách trình bày thì sẽ phải rất cẩn thận với các chi tiết dễ bị bỏ qua vì bức tranh đẹp trước mắt B-) B-)

Cụ thể lần này em lại có góp ý như sau:
Định lý ở cuối mục 7d hình như chưa mạnh như vậy được. Vì khi $d$ tăng lên thì $\eta$ cũng tăng theo (như trong chứng minh). Nói cách khác, khi $d$ tăng lên thì “gap” phải “thu hẹp” lại thì mới có hi vọng vẫn là NP-hard (ít nhất là theo cách chứng minh của ta). Nếu góp ý này sai một cách tầm thường, rất mong được bỏ qua

Em chưa có đủ ability để đọc survey của Linial et. al. cũng như paper của Feige nên không biết khẳng định mạnh nhất sẽ như thế nào. Cứ chậm mà chắc cõ lẽ vẫn hơn.

Reply
Ngô Quang Hưng

Posted 20/05/2009 at 10:25 am | Permalink

@Thinh:

Cảm ơn, đây là vấn đề ngôn ngữ.

Ý tôi muốn viết là “Với mọi $d \geq 15$ , tồn tại $\eta >0$ , blah blah blah. Sẽ sửa lại.

Reply
Thinh Nguyen

Posted 20/05/2009 at 6:22 pm | Permalink

$d \geq 29$ mới đúng ạ vì $d$ trong định lý phải bằng $d$ của expander graph nhân $2$ cộng $1$ .

Thêm nữa là Gap-Max-3SAT(Ed)( $1, \eta$ ) vì mỗi biến $y_{i,j}$ xuất hiện trong chính xác $2d+1$ (với the latter $d$ ở đây là của expander). Việc này liên quan đến phát biểu của định lý và bài tập 2.

Em đang pó tay với bài tập 2. Anh Hưng có thể cho hint được không ạ (sau khi phát biểu lại problem statement ). Đương nhiên bước sang mục 7e, ta có thể coi như đã có gap-preserving reduction trong bài tập 2 rồi và đọc ngon lành

Bài tập 3: (chờ comment sau)

Reply
Ngô Quang Hưng

Posted 20/05/2009 at 7:53 pm | Permalink

Thanks Thinh,

đã sửa thành 29.

Bài tập 2 dùng các kỹ thuật “well-known”. Đại khái, clause nào thiếu biến thì có thể thêm vào literal mới $y$ , rồi thêm vào các clauses $(\bar y \vee z_1 \vee z_2)$ , $(\bar y \vee \bar z_1 \vee z_2)$ , $(\bar y \vee z_1 \vee \bar z_2)$ , $(\bar y \vee \bar z_1 \vee \bar z_2)$ . Sau quá trình này thì chỉ cần chữa vụ “mỗi biến xuất hiện $d$ lần. Gom các biến xuất hiện dưới $d$ lần lại (gọi chúng là biến “thiếu tháng”). Sau đó thêm vào một mớ biến dummy rồi thêm các clause dùng các biến “thiếu tháng” và các biến dummy mới. Phải cẩn thận tính xem cần bao nhiêu biến dummy và dàn xếp chúng với các biến “thiếu tháng” như thế nào. Chọn d=29 cho dễ làm.

Reply
Thinh Nguyen

Posted 21/05/2009 at 5:04 am | Permalink

Có làm bài tập mới biết mình còn kém

Tuy rằng các instances thu được trong mục 7d chỉ là tập con của Gap-Max-3SAT(d)( $1, \eta$ ) nhưng ta sẽ làm trong trường hợp tổng quát để luyện tập, dù rằng các tính toán sẽ cồng kềnh hơn đôi chút.

Kĩ thuật “ $3$ -hoá” đã rất quen thuộc trong phép qui dẫn cổ điển từ SAT về 3-SAT. Cần chú ý là giá trị $d$ sẽ bị tăng lên nhiều nhất là 4 lần (trong trường hợp có clause 1 literal).

Kĩ thuật “ $d$ -hoá” thì có vẻ khó hơn. Giả sử có $n$ biến “thiếu tháng” với số tháng bị thiếu tương ứng là $d_1, d_2, \dots , d_n$

Reply
RongChoi

Posted 21/05/2009 at 5:17 am | Permalink

Reduction từ Gap-Max-E3SAT về Gap-Max-3SAT sử dụng Expander hay một cách bất ngờ!

Hơi tiếc là cái Reduction này không cho ta length-preserving witness. Số biến trong $\psi$ bằng cỡ input length của $\varphi$ . Do ở đây là 3SAT nên m = poly(n). Nhưng giả dụ ta áp dụng cho trường hợp tổng quát thì rất có thể witness của $\psi$ sẽ có chiều dài bằng exp() chiều dài của witness của $\varphi$ .

Vì đây là 2 bài toán “cùng loại” nên rất có thể sẽ có một reduction tốt hơn cho length-preserving witness?

Reply
Thinh Nguyen

Posted 21/05/2009 at 5:24 am | Permalink

Chú ý thêm là sau khi “3-hoá” thì cái “gap” của ta cũng bị “thu hẹp” một cách đáng kể (nhưng vẫn là constant $\eta$ ). Chưa tính bước “d-hoá” còn lại thì đã có thể khẳng định là kết quả thu được sẽ rất yếu. Để đạt được result of hardness mạnh quả là khó.

Reply
Thinh Nguyen

Posted 21/05/2009 at 6:33 am | Permalink

Để đảm bảo progress em đề nghị anh Hưng Ngô kết thúc nốt bước “d-hoá” (hoặc nếu có thể thì chỉ cho bọn em cách improve cái result hiện đang rất yếu).

Reply
Ngô Quang Hưng

Posted 21/05/2009 at 6:41 am | Permalink

Ý Thịnh nói “yếu” là $\rho$ gần 1 quá hả? Miễn là hằng số là được rồi. (Nhớ là $d$ cũng là hằng số, nên cái gap của bạn phụ thuộc vào $d$ cũng không sao.)

Kết quả mạnh nhất cũng chỉ có gap là $7/8$ thôi, mà khi đó phải hy sinh perfect completeness nữa. Nếu khăng khăng với perfect completeness thì tôi không biết kết quả mạnh nhất là gì (à, cũng $7/8$ nhờ GLTS ở FOCS 1998). Cái gap $7/8$ thì bạn phải chờ xong expanders, đến Fourier analysis of long code rồi mới tới. Be patient

Reply