PCP 3 — Khó xấp xỉ, gap-producing reductions, FGLSS reduction

7. Cơ bản về chứng minh sự khó xấp xỉ

Trong bài trước, chúng ta đã chứng minh rằng định lý PCP tương đương với Gap-Max-E3SAT(1,\rho) là NP-Hard với một hằng số \rho>0 nào đó. Chúng ta sẽ thấy rằng định lý PCP cũng tương đương với một số gap-problems khác là NP-Hard, ví dụ như bài toán Gap-LabelCover sẽ định nghĩa sau. Chúng ta quan tâm đến sự tương đương này vì hai lý do:

(1) Từ NP-Hardness của một gap-problem ta suy ra tính khó xấp xỉ của bài toán tối ưu tương ứng. Ví dụ, chúng ta đã chứng minh rằng từ tính chất NP-Hard của Gap-Max-E3SAT(1,\rho) có thể suy ra rằng bài toán Max-E3SAT không thể xấp xỉ được đến tỉ lệ \rho+\epsilon với \epsilon > 0 nhỏ tùy ý. Đây là cách duy nhất chúng ta biết để chứng minh rằng một bài toán là khó xấp xỉ (nếu định nghĩa “khó” = NP-hard).

(2) Ta sẽ chứng minh định lý PCP bằng cách chứng minh rằng một gap-problem (cụ thể là Gap-Constraint-Graph) là NP-hard.

Trong bài này và khoảng 2 bài tới, tôi sẽ đào sâu hơn nữa về việc chứng minh tính khó xấp xỉ của một số bài toán quan trọng như Max-E3SAT, Max-Clique, Max-Cut, v.v. Một số kết quả (như của Hastad) mạnh đến mức đáng kinh ngạc — cho thấy sức mạnh của định lý PCP. Một số kết quả khác thì lại dựa trên một conjecture gần đây (UGC của Khot) mà chưa ai chứng minh được đúng hay sai — cho thấy chúng ta vẫn chưa hiểu rõ lắm về PCP. Các bài này nhằm mục đích giới thiệu các kỹ thuật chứng minh độ khó xấp xỉ, để độc giả phát triển trực quan về các PCP verifiers, và để phát triển một số kỹ thuật (như Fourier analysis of Boolean functions, expander graphs, random walks) phục vụ cho bản thân chứng minh định lý PCP.

7.a. Làm thế nào để chứng minh rằng xấp xỉ một bài toán nào đó là NP-Hard?

Hãy xét một bài toán tối ưu hóa \Pi nào đó. Giả sử \Pi là bài toán maximization, như Max-Clique, Max-Independent-Set, hay Max-E3SAT. Để chứng minh rằng xấp xỉ \Pi đến một tỉ lệ \rho+\epsilon là NP-Hard với mọi \epsilon, chúng ta định nghĩa một bài toán Gap-\Pi(c,s) và chứng minh nó là NP-hard; trong đó \rho = s/c. Nếu \Pi là bài toán minimization, thì làm tương tự, nhưng có một số bất đẳng thức đổi ngược lại và được định nghĩa như sau. Với một đồ thị G bất kỳ, gọi \omega(G) là kích thước clique lớn nhất của G (còn lại là clique-number của G). Một input graph của bài Gap-Max-Clique(c,s) thỏa mãn điều kiện là: hoặc \omega(G) \geq c hoặc \omega(G) \leq s. Chú ý rằng c,s có thể phụ thuộc vào kích thước của input graph G.

Bổ đề sau đây là hiển nhiên. Đây là lần cuối cùng chúng ta ghi rõ ra một bổ đề kiểu này. Từ sau trở đi, tính chất NP-hard của một gap-problem tự nhiên phải được hiểu là tính chất NP-hard của việc xấp xỉ bài toán tối ưu tương ứng.

Bổ đề: nếu Gap-Max-Clique(c,s) là NP-hard với các hàm số c, s nào đó (với nhỏ tùy ý.

Làm thế nào để chứng minh một gap-problem là NP-Hard? Chúng ta thiết kế một reduction (nghĩa là một polynomial time algorithm) từ một bài toán NP-hard đã biết nào đó đến gap-problem nọ. Hãy lấy Max-Clique làm ví dụ. Giả sử L là một bài toán NP-hard đã biết. Ta cần thiết kế một thuật toán xây dựng một đồ thị G_x cho mỗi input x của bài toán L, sao cho:

  • Nếu x \in L thì \omega(G_x) \geq c
  • Nếu x \notin L thì \omega(G_x) \leq s

Một reduction như thế thường được gọi là một gap-producing reduction. Cái gap được đo bằng tỉ lệ s/c. Khi có một reduction như thế, sẽ là NP-hard để phân biệt giữa các instances G của Max-Clique thỏa \omega(G) \geq c và các instances thỏa \omega(G) \leq s.

7.b. Làm thế nào để thiết kế gap-producing reduction?

Trước định lý PCP, có tồn tại gap-producing reductions cho một số cực ít (đếm trên đầu ngón tay) các bài toán tối ưu cổ điển. (Ví dụ Gap-TSP là khó, reduced từ Hamiltonian Cycle.) Chỉ đến định lý PCP ta mới xây dựng được các gap-producing reduction “tự nhiên” cho rất nhiều các bài toán. Có thể nói là định lý PCP đã “đả thông kỳ kinh bát mạch” để môn hardness of approximation có cơ hội phát triển.

Có một vài kỹ thuật chính để thiết kế một gap-producing reduction.

  1. Bắt đầu từ định lý PCP, chúng ta biết rằng bất kỳ bài toán NP-complete L nào cũng có một (O(\log n),O(1))-restricted verifier V. Dùng V làm sub-routine để thiết kế cái gap-producing reduction.
  2. Bắt đầu từ một bài toán L đã “có sẵn” cái gap, chúng ta reduce nó về gap-\Pi với một bài toán \Pi đang xét. Như vậy, cái reduction này không hẳn là “produce gap” mà là “preserve gap”. Chúng ta sẽ thấy rằng, có nhiều NP-hard reduction thông thường cũng phần nào “bảo tồn” cái gap.
  3. Định lý PCP như đã phát biểu thì hơi “yếu” để có thể chứng minh các kết quả hardness of approximation mạnh. Chúng ta có thể chứng minh các định lý PCP “mạnh” hơn (với các tham số đặc biệt hơn) để phục vụ cho một gap-producing reduction cụ thể nào đó.
  4. Cộng với một số kỹ thuật cơ bản dùng để “khuếch đại” gap sẽ bàn trong các bài tới: kỹ thuật “lặp” thông thường, “lặp” với expanders, “lặp song song” (của Ran Raz).

Chúng ta đã thấy một minh họa của kỹ thuật 1 khi chứng minh trong bài trước rằng Gap-Max-E3SAT là NP-hard. Trong bài này, ta sẽ minh họa thêm kỹ thuật số 1 bằng FGLSS reduction

7.c. FGLSS reduction

FGLSS là một reduction khá tổng quát. Xét một (r,q)-restricted verifier V cho một ngôn ngữ L \in \mathsf{PCP}_{c,s}[r,q], với c,s,r,q là các tham số bất kỳ. Xét một input x (mà ta không biết là có thuộc L hay không). Một transcript cho V là một bộ \langle R, Q_1,a_1,Q_2,a_2,\dots,Q_q,a_q \rangle; trong đó R là một chuỗi r random bits, Q_i là query thứ i của Va_i là “câu trả lời” tương ứng với query Q_i. (Mỗi query là một index vào “chứng minh” \pi, và mỗi câu trả lới là bit 0/1 ở vị trí được hỏi trong \pi.)

Sau khi lấy r random bits R, verifier sẽ chấp nhận hoặc từ chối input x tùy theo các câu trả lời cho các queries như thế nào. Nếu verifier chấp nhận thì cái transcript được gọi là accepting transcript. Hai accepting transcripts gọi là nhất quán với nhau nếu như một câu hỏi xuất hiện ở cả hai transcript thì có cùng câu trả lời. (Nghĩa là nếu Q_i của transcript này bằng với Q'_j của transcript kia thì a_i của transcript này phải bằng a'_j của transcript kia.)

Đến đây, xây dựng một đồ thị G_x=(V_x,E_x) như sau. V_x là tập hợp tất cả các accepting transcripts. Còn E_x là các cạnh nối các cặp accepting transcripts nhất quán với nhau. Dễ thấy rằng |V_x| \leq 2^{r+q}. Ta có thể thêm một số đỉnh đơn lẻ vào V_x để cho |V_x| = 2^{r+q}.

Lưu ý quan trọng: tập tất cả các đỉnh của V_x với cùng một random string R tạo thành một independent set. Tại vì: cùng một random string thì sẽ cùng các câu hỏi, do verifier V là deteministic verifier nếu ta cố định các random bits. Mà hai transcripts khác nhau có cùng các câu hỏi thì phải khác một câu trả lời nào đó, nếu không thì sẽ là cùng một transcript. Như vậy, hai transcripts với cùng một random string không thể nhất quán với nhau. Chú ý rằng verifier này là non-adaptive, nghĩa là nó tạo toàn bộ các câu hỏi trước khi gửi câu hỏi, không “adapt” câu hỏi kế tiếp dựa trên câu trả lời của câu hỏi trước.

Từ lưu ý trên, ta có thể chứng minh hai điều sau đây không khó khăn gì lắm.

(a) nếu x \in L, nghĩa là tồn tại một chứng minh \pi sao cho \text{Prob}[V^\pi \text{ accepts } x] \geq c, thì w(G_x) \geq c2^r = c|V_x|/2^q.

(b) nếu x \notin L, nghĩa là với bất kỳ chứng minh \pi nào ta cũng có \text{Prob}[V^\pi \text{ accepts } x] \leq s, thì w(G_x) \leq s2^r = s|V_x|/2^q.

Để thấy (a) đúng, chỉ cần xét tất cả các transcripts mà câu trả lời đến từ chứng minh \pi nọ. Do các câu trả lời đến từ cùng một chứng minh, các transcripts này nhất quán với nhau, và vì thế tạo thành một clique. Tổng số đỉnh của clique này ít nhất là bằng tổng số random string R làm cho verifier chấp nhận. Do verifier chấp nhận x với xác suất \geq c, tổng số đỉnh của clique này \geq c2^r.

Để thấy (b) đúng, giả sử như tồn tại một clique với kích thước > s2^r. Các transcripts là các đỉnh của clique này nhất quán với nhau. Ta có thể lấy hội của các câu trả lời để tạo ra một chứng minh \pi mà xác suất verifier chấp nhận >s, mâu thuẫn với điều kiện x \notin L.

Chú ý rằng cái FGLSS reduction có running time là poly(|x|, 2^{r+q}). Do đó

Định lý. Nếu \mathsf{NP} \subseteq \mathsf{PCP}_{c,s}[r,q] và nếu 2^{r+q} = \text{poly}(n), thì chúng ta không thể xấp xỉ Max-Clique đến tỉ lệ s/c+\epsilon với bất kỳ \epsilon>0 nào.

Chứng minh. Chọn một ngôn ngữ NP-complete L \in \mathsf{NP} bất kỳ. Do \mathsf{NP} \subseteq \mathsf{PCP}_{c,s}[r,q], ta biết L \in \mathsf{PCP}_{c,s}[r,q]. Do đó, cái FGLSS reduction chạy trong poly-time, và thỏa mãn hai điều kiện (a) và (b) ở trên. Từ đó, bài toán Gap-MaxClique(c|V_x|/2^q,s|V_x|/2^q) là NP-hard, dẫn đến kết quả không thể xấp xỉ được như trong phát biểu định lý.

QED

Hệ quả. Không thể xấp xỉ Max-Clique đến bất kỳ tỉ lệ hằng số \rho>0 nào.

Chứng minh. Định lý PCP nói rằng \mathsf{NP} \subseteq \mathsf{PCP}_{1,1/2}[O(\log n), O(1)]. Bằng cách chạy PCP verifier \log_2(1/\rho) lần độc lập, dễ thấy \mathsf{NP} \subseteq \mathsf{PCP}_{1,\rho}[O(\log n), O(1)]. (Nhớ rằng \rho là hằng số.) Áp dụng định lý trên.

QED

Hệ quả trên không phải là kết quả mạnh nhất ta biết về Max-Clique. Trong các bài tới, chúng ta sẽ thảo luận vài kỹ thuật “khuếch đại” gap để chứng minh kết quả tốt hơn.

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

11 Comments

  1. Thinh Nguyen
    Posted 19/05/2009 at 5:54 am | Permalink

    Em mat 1 tieng dong ho moi absorb duoc phan nao cai “FGLSS reduction”. Easily understandable nhung ma khong ro motivation j khien cac authors nghi den khai niem “accepting transcript” huu ich nhu vay de chi ra connection giua PCP va Hardness of Approximation. Reduction nay kha noi tieng trong PCP theory.

    Em rat mong cho xem cac techniques va ca cac objects quan trong o bai sau 😀 🙂

  2. Posted 19/05/2009 at 6:27 am | Permalink

    @Thinh: như tôi có viết trong Bài 1, FGLSS là co-winner của giải Godel 2001 — nhờ chỉ ra cái “PCP connection” này. Nói cách khác, bài báo FGLSS được giải vì đã chỉ cho chúng ta một bước nhảy vọt về mặt tư duy (về hardness of approximation). Do đó, chúng ta cần thời gian “absorb” nó là phải. Điều kỳ diệu là cái reduction này thật sự rất đơn giản.

  3. Thinh Nguyen
    Posted 19/05/2009 at 8:31 pm | Permalink

    Em nghi la trong “Chu y quan trong” cua FGLSS reduction can notice them la Verifier cua ta la non-adaptive. Khi co R co dinh thi V se hoi nhung cau hoi Q_i giong het nhau bat ke answers a_i nhan duoc nhu the nao.

  4. Posted 19/05/2009 at 8:38 pm | Permalink

    Cảm ơn Thịnh. Sẽ sửa.

    Tôi đọc bài FGLSS cách đây 4, 5 năm rồi nên không nhớ rõ lắm; nhưng tôi tin là cái reduction vẫn “work” cho adaptive verifier sau khi sửa lại một chút. Đang viết PCP 5 — expanders, nhưng chắc phải mai mới xong một nửa.

  5. Posted 20/05/2009 at 12:49 am | Permalink

    Non-adaptive vs. adaptive verifier bạn Thinh Nguyen đề cập rất đáng quan tâm. Tuy vậy FGLSS reduction có lẽ chạy cho cả hai.
    Điều quan trọng là “hai transcripts với cùng một random string không thể nhất quán với nhau” sẽ vẫn đúng trong cả 2 trường hợp:
    Nếu ta fix random string R thì câu hỏi đầu tiên của Verifier trong hai transcripts là như nhau. Nếu câu trả lời cho câu hỏi đầu tiên này trong hai transcripts khác nhau thì ta kết luận chúng không nhất quán. Nếu hai câu trả lời giống nhau thì câu hỏi thứ 2 trong hai transcripts sẽ lại là như nhau (w.r.t Adaptive Verifier). Cứ như vậy ta thấy chừng nào câu trả lời còn giống nhau thì câu hỏi tiếp theo còn giống nhau. Và vì hai transcripts khác nhau nên sẽ có lúc tới điểm không nhất quán.

  6. Thinh Nguyen
    Posted 20/05/2009 at 2:30 am | Permalink

    @RongChoi: Rất cảm ơn anh RongChoi vì nhận xét chính xác. Em sẽ suy nghĩ kĩ hơn trước khi đưa ra các góp ý về sau 🙂

  7. Posted 20/05/2009 at 10:38 am | Permalink

    Hello RongChoi, Thinh,

    Thật ra để chứng minh FGLSS “work” cho adaptive verifier thì còn phải xác minh là tổng số đỉnh của G_x là polynomial. Tại vì tổng số đỉnh sẽ không còn là 2^{q+r} nữa. May mà, trong trường hợp của định lý PCP thì q là hằng số, cho nên |V_x| vẫn là polynomial và mọi thứ vẫn chạy. Nhưng phát biểu của định lý trên không còn đúng cho trường hợp adaptive verifier nếu q là super-constant.

  8. Posted 20/05/2009 at 11:55 am | Permalink

    Hi anh Hưng,
    Số đỉnh vẫn là 2^{r+q} chứ nhỉ? Với mỗi R cố định và mỗi bộ câu trả lời a_1,\ldots,a_q, thì chỉ tương ứng không quá 1 bộ câu hỏi.

  9. Posted 20/05/2009 at 12:15 pm | Permalink

    À đúng rồi. Cảm ơn RongChoi. Hồi nãy không hiểu sao lại nghĩ là tổng số đỉnh là 2^r|\pi|^q.

  10. Posted 20/05/2009 at 1:25 pm | Permalink

    Nếu câu trả lời không phải là bit thì đúng là phải dùng cái bound anh Hưng nghĩ ^^

  11. Thinh Nguyen
    Posted 20/05/2009 at 6:11 pm | Permalink

    Hi mọi người,

    Cũng may là các dummy vertices thêm vào không ảnh hưởng đến chứng minh của ta 😀
    Như vậy FGLSS reduction đã được “absorb” gần như xong. Tạm thời có thể coi là xong một breakthrough.

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>

*
*