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.

  • 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'}\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}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_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
Chủ đề : Lý thuyết tính toán, Thuật ToánBookmark the permalink. Trackbacks are closed, but you can post a comment.

10 Comments

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

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

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

  4. 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)

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

  6. 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 😀

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

  8. 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ó.

  9. 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).

  10. 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 🙂

Post a Comment

Your email is never published nor shared. Required fields are marked *

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*
*