Thư viện bài, chuyên mục ‘Thuật Toán’

GT 6: Thử nhóm bất ứng biến giải mã nhanh

Ngô Quang Hưng | 29 tháng 01, 2010 | Bản để in Bản để in

6. Thử nhóm bất ứng biến giải mã nhanh

6.1. Ý tưởng của Kautz-Singleton

Hồi 1964, Kautz và Singleton đề xuất cách xây dựng ma trận {d}-phân-cách dựa trên hai ý tưởng chính. Thứ nhất là nếu các cột của ma trận có “cân nặng” (số số {1} trên cột) đủ lớn và nếu hai cột bất kỳ có phần giao đủ nhỏ thì ma trận sẽ là ma trận phân cách. Thứ hai là ta có thể dùng phương pháp nối mã (code concatenation) để xây dựng một ma trận thỏa tính chất thứ nhất. Chúng ta thảo luận ý tưởng của Kautz-Singleton trước, sau đó chỉ ra cách dùng ý tưởng này và một ý mới để xây dựng ma trận phân cách giải mã nhanh được.

Bổ đề 1 Gọi {{\bf M}} là một ma trận nhị phân {t \times N} mà mỗi cột có cân nặng ít nhất là {w}, và phần giao của hai cột bất kỳ (các số {1} chung của hai cột) có lực lượng nhiều nhất là {\lambda}. Thì, {{\bf M}} là ma trận {d}-phân-cách với bất kỳ {d} nào thỏa mãn {d\lambda+1 \leq w}. Cụ thể là {{\bf M}} sẽ là ma trận {\left\lfloor \frac{w-1}{\lambda} \right\rfloor}-phân-cách.

Bổ đề này dễ chứng minh. Ta nói tiếp ý tưởng thứ hai. Trước hết hãy định nghĩa phép nối mã.

Gọi {C_{\text{out}}} là một mã {(n_1,k_1)_q}, nghĩa là một ánh xạ từ {\mathbb F_q^{k_1}} vào {\mathbb F_q^{n_1}}, trong đó {q = 2^{k_2}}. (Phép nối mã có thể định nghĩa tổng quát hơn, nhưng ta không cần điều đó.) Như vậy, mỗi ký tự mã của {C_{\text{out}}} là một thành viên của tập {\mathbb F_q} gồm {2^{k_2}} phần tử, và vì thế cũng có thể xem như một thành viên của tập {\mathbb F_2^{k_2} = \{0,1\}^{k_2}}. Mỗi một từ mã của {C_{\text{out}}} có {n_1} vị trí. Mã {C_{\text{out}}} sẽ được gọi là mã ngoài (outer code).

Đọc tiếp toàn bài »

Chuyên mục: Combinatorics & Lý thuyết mã hóa & Thuật Toán | Bình luận (2) »

GT 5: Sơ lược lý thuyết mã hóa

Ngô Quang Hưng | 26 tháng 01, 2010 | Bản để in Bản để in

5. Sơ lược lý thuyết mã hóa

Claude Shannon là cha đẻ của lý thuyết thông tin và lý thuyết mã hóa. Sẽ không có truyền thông hiện đại nếu không có Shannon. Nhà toán học lỗi lạc Kolmogorov từng nói về Shannon như sau: “Trong thời buổi mà kiến thức nhân loại càng lúc càng đuợc chuyên môn hóa, Claude Shannon là một nhà khoa học ngoại lệ. Shannon kết hợp các ý tưởng toán học sâu sắc với các hiểu biết rộng và cụ thể của các vấn đề quan trọng bậc nhất của công nghệ. Shannon là một trong những nhà toán học vĩ đại nhất đồng thời là một trong những kỹ sư giỏi nhất trong vài thập niên qua”. Nếu câu nói đó được phát biểu lúc này, thì phải thay “vài thập niên qua” bằng “thế kỷ 20″. Bài này duyệt qua một số kiến thức cơ bản về lý thuyết mã hóa cần cho thử nhóm.

5.1. Ý tưởng của Shannon (và Hamming)

Ý tưởng chính của lý thuyết mã hóa là thêm thông tin vào từng thông điệp trước khi gửi đi để bên nhận có thể tự phát hiện lỗi hoặc thậm chí tự sửa lỗi xảy ra trên đường truyền. Hai tham số chính của một mã là tỉ lệ (rate) của thông tin nguyên thủy trên thông tin gửi đi, và khả năng chịu đựng lỗi — số lỗi tối đa mà mã có thể dùng để kiểm tra hoặc sửa lỗi.

Cụ thể hơn, giả sử ta làm việc trên an-pha-bê {\Sigma}. Trong truyền thông số thì thông thường {\Sigma = \{0,1\}^m} với số tự nhiên {m} nào đó vì thường chỉ có 2 bits {0} và {1}. Trong lý thuyết mã hóa thì {\Sigma} có thể tổng quát hơn, là một trường {\mathbb F_q} chẳng hạn. Chuyển từ an-pha-bê {\mathbb F_q} sang an-pha-bê nhị phân không khó khăn gì. Nhưng ta cứ xét một an-pha-bê tổng quát trước đã. Giả sử mỗi thông điệp gửi đi có chiều dài {k}, nghĩa là mỗi thông điệp gửi đi là một vector trong {\Sigma^k}. Thay vì gửi một thông điệp {{\bf x} \in \Sigma^k}, ta gửi {{\bf y} = E({\bf x})} là ảnh của {{\bf x}} dưới ánh xạ mã hóa {E: \Sigma^k \rightarrow \Sigma^n}. Chúng ta cần {{\bf y}} chứa nhiều thông tin hơn {{\bf x}}, để cho bên nhận — dù có nhận một bản bị lỗi của {{\bf y}} — thì vẫn có thể hồi phục lại {{\bf x}}. Do đó {n > k}.

Đọc tiếp toàn bài »

Chuyên mục: Combinatorics & Lý thuyết mã hóa & Thuật Toán | Bình luận »

GT 4: Bassalygo, Erdős, và Sperner

Ngô Quang Hưng | 29 tháng 12, 2009 | Bản để in Bản để in

4. Chặn dưới

Leonid Bassalygo là một học trò giỏi của người khổng lồ Kolmogorov. Từ những năm 1970, ông đã có nhiều đóng góp cơ bản trong lý thuyết thông tin, lý thuyết mã hóa, và lý thuyết các mạng chuyển mạch (switching networks). Có nhiều định lý và chặn mang tên ông. Ví dụ như chặn Elias-Bassalygo. Hiện nay ông là tổng biên tập tờ Problems in Information Transmission. Tạp chí tiếng Nga này có nội dung và tầm tương tự như tạp chí IEEE Transactions on Information Theory. Bài này sẽ thảo luận một chặn của Bassalygo cho đại lượng {t(d,N)}, số hàng nhỏ nhất của một ma trận {d}-phân-cách với {N} cột.

Xét một ma trận {d}-phân-cách {{\bf M}=(m_{ij})} với {t} hàng và {N} cột. Nhớ rằng mỗi cột {j} của ma trận có thể được đánh đồng với tập con {\{ i \ | \ m_{ij} =1 \}} của tập {[t] = \{1,\dots,t\}}. Bộ {\mathcal F} gồm {N} tập hợp này thỏa tính chất sau đây: lấy {d+1} tập bất kỳ {F_0, \dots, F_{d+1} \in \mathcal F} thì ta luôn có {F_0 \not\subseteq F_1 \cup \cdots \cup F_d}. Tính chất này tiếng Anh gọi là tính chất {d}-cover-free của bộ tập hợp {\mathcal F}. (Dịch “{d}-cover-free” sang tiếng Việt thế nào nhỉ?) Hơn nữa, xét một tập {F \in \mathcal F} bất kỳ với lực lượng {|F| = w \leq d}, thì {F} phải chứa một phần tử mà không tập nào khác có. Tại vì, nếu mỗi phần tử của {F} đều thuộc một tập khác thì {F} sẽ nằm trong hội của nhiều nhất {w \leq d} tập khác, mẫu thuẫn với tính chất {d}-phân-cách. Phần tử chỉ riêng {F} có gọi là phần tử riêng của {F}. Tổng quát hơn, một tập con chỉ chứa trong {F} gọi là một tập con riêng của {F}.

Do chỉ có tổng cộng {t} phần tử, sẽ chỉ có nhiều nhất là {t} phần tử riêng, và vì thế nhiều nhất là {t} thành viên của {\mathcal F} với lực lượng {\leq d}. Cụ thể hơn, gọi {n(w)} là số tập với lực lượng {w}, thì ta có

\displaystyle \sum_{w \leq d} n(w) \leq t. \ \ \ \ \ (1)

Đọc tiếp toàn bài »

Chuyên mục: Combinatorics & Thuật Toán | Bình luận (1) »

GT 3: Ứng dụng trong dòng dữ liệu và bảo mật

Ngô Quang Hưng | 17 tháng 12, 2009 | Bản để in Bản để in

3. Vài ứng dụng của thử nhóm bất ứng biến

Muthu Muthukrishnan là một khoa học gia máy tính có rất nhiều đóng góp nặng ký trong nhiều nhánh khác nhau: cơ sở dữ liệu, thuật toán, dòng dữ liệu, v.v. Gần đây anh chuyển về Google làm về các thuật toán ad bidding, một nhánh “hot” liên kết kinh tế học và KHMT; có thể xem là một phần của môn “kinh tế tính toán” — còn non trẻ nhưng rất thú vị. Muthukrishan cũng là một trong các khoa học gia vui vẻ dễ gần nhất mà tôi biết. Một lần giới thiệu Muthu nói chuyện, tôi hỏi anh muốn giới thiệu như thế nào, anh bảo giới thiệu thế này: “đây là Muthu, anh ta sẽ nói chuyện”. Muthukrishnan và Cormode mấy năm trước có một bài báo rất thú vị ở hội nghị FUN với nhan đề “Làm thế nào để tăng tỉ lệ nhận bài của các hội nghị đỉnh”. Tôi đã giới thiệu bài này trong một blog post cũ.

Hai bài trước đã bàn về khái niệm thử nhóm bất ứng biến tổ hợp và một vài kết quả cơ bản. Trước khi nói đến các kết quả sâu hơn thì ta quay lại mô tả chi tiết một vài ứng dụng. Ứng dụng đầu tiên do Cormode và Muthukrishnan đề xuất là cho một bài toán trong dòng dữ liệu.

Đọc tiếp toàn bài »

Chuyên mục: Bảo mật và mật mã học & Thuật Toán | Bình luận »

GT 2: Phân Ly và Phân Cách

Ngô Quang Hưng | 15 tháng 12, 2009 | Bản để in Bản để in

( tiếp theo bài trước ).

2. Ma trận phân ly và ma trận phân cách

Tiến Sĩ Nguyễn Quang A là một trong các trí thức hàng đầu của Việt Nam hiện nay. Tôi không biết gì về các công việc làm ăn của anh Quang A, nhưng tôi biết anh đã một tay cáng đáng tủ sách S.O.S. (dù các bản dịch Popper, Hayek hơi trúc trắc, cố gắng này thực sự là đáng nể phục và rất quan trọng), anh còn là nguyên viện trưởng viện IDS vừa tuyên bố giải thể để phản đối quyết định 97 của chính phủ, là một trong số rất hiếm những tiếng nói phản biện xã hội có nội lực ở Việt Nam hiện nay. Tôi cũng không biết tường tận tiểu sử TS Nguyễn Quang A, nhưng tôi biết anh có một bài báo chuyên ngành chất lượng liên quan đến vấn đề thử nhóm. Để mô tả kết quả trong bài báo này và các kết quả khác, chúng ta cần một khái niệm mới gọi là ma trận {d}-phân cách.

Hãy quay lại với bài toán thử nhóm bất ứng biến. Giả sử ta có {N} mẫu máu, trong đó ta biết trước rằng có nhiều nhất là {d} mẫu dương tính. Cách thiết lập bài toán như thế này gọi là “thử nhóm tổ hợp” (combinatorial group testing), thích hợp với một số ứng dụng nhất định. Trong một số ứng dụng khác thì chúng ta không biết chặn trên {d} này, và có thể phải giả sử hoăc học một phân bố xác suất của các mẫu máu dương tính. Đó là thiết lập bài toán “thử nhóm xác suất” (probabilistic group testing), nhánh nghiên cứu còn rất mở và chúng ta không có nhiều kết quả tốt, đúng như anh Xuân Long đã bình luận sắc bén trong bài trước.

Đọc tiếp toàn bài »

Chuyên mục: Combinatorics & Thuật Toán & Xác suất & thống kê | Bình luận (4) »

GT 1: Bệnh giang mai, đại số, hồi phục tín hiệu thưa, và dòng dữ liệu

Ngô Quang Hưng | 14 tháng 12, 2009 | Bản để in Bản để in

1. Đại số và bệnh giang mai

Hòa thượng (HT) Thích Học Toán là chuyên gia đại số hàng đầu thế giới. (Tôi học đòi cách viết bài của giáo sư Richard Lipton mà tôi rất thích.) Gần đây HT lại thành celebrity sau bầu chọn của tạp chí Time. Nhất định sẽ có nhiều bạn hỏi thế công trình của HT có ý nghĩa như thế nào trong cuộc sống, hoặc ít nhất cũng tìm cách “diễn Nôm” ý nghĩa của đóng góp của HT. Để trả lời các câu hỏi kiểu đó, xin mạn phép gợi ý 3 hướng trả lời sau đây. (Hướng cuối cùng là liên quan đến KHMT, cho nên các bạn hủ máy tính có thể nhảy xuống đó mà đọc, bỏ qua các hướng đầu.)

  1. Kể lại một truyền thuyết về Euclid, do Stobaeus kể lại:

    Khi một chú học trò hỏi Euclid: “chúng ta học hình học thì được cái gì?”, Euclid gọi một anh nô lệ vào bảo: “cho nó một đồng xu, vì nó muốn kiếm lời từ cái nó học”.

  2. Kể lại câu chuyện của Cụ Hinh và Anh La:

    Nghe thiên hạ đồn rằng có bộ kinh tiếng Phạn nọ rất thâm sâu. Cụ Hinh cầu cạnh anh La giảng giải cho. Anh La nhíu mày, rít thuốc, nhâm nhi cà fê cả buổi sáng. Đến chiều, anh La dịch toàn bộ kinh sang tiếng Bồ.

    Cụ Hinh xem xong gật gù tán thưởng.

  3. Đại số có ứng dụng trong trị bệnh giang mai.

Đọc tiếp toàn bài »

Chuyên mục: Bảo mật và mật mã học & KHMT và sinh học & Thuật Toán & Xác suất & thống kê | Bình luận (6) »

Một bài tập lớp mạng máy tính

Ngô Quang Hưng | 21 tháng 10, 2009 | Bản để in Bản để in

Học kỳ này tôi dạy lớp mạng máy tính. Tôi thiết kế một bài tập mà cá nhân tôi rất thích vì nó chứa các thành tố của cả mạng lẫn thuật toán (quy hoạch động). Ý tưởng của bài tập này đến từ một bài báo mà anh Hà Trần Đức và tôi viết mấy năm trước. Chia sẻ bài tập này với các bạn ở đây cho vui. Do cut-and-paste, đoạn sau đây viết bằng tiếng Anh.

Problem 1. In this question, we explore how potentially a P2P design is more efficient than a central sever design for file distribution. However, to make it juicier, we will explore this issue from a computer worm propagation context.

The Slammer worm was a very famous computer worm, very destructive, infected 75000 victims within 10 minutes in January of 2003. Each instance of the worm has size 404 bytes. We will simplify the problem for the worm writer a little. Let’s assume that once an infected computer A transmitted the worm (404 bytes) to computer B, computer B is infected and thus can propagate the worm further on its own. If you were a worm writer wanting to design an infection strategy for your worm, you’ll have to do some back-of-the-envelop computation similar to this problem.

Suppose the worm writer wants to infect 1 million home computers, each of which has an ADSL connection whose upload speed is 400Kbps and whose download speed is 1.4Mbps. This population of 1 million computers is called the vulnerable population. Also suppose that the propagation delay from any machine to another machine on the Internet is 50ms.

Consider the following two scenarios:

  • Suppose initially a really fast server is infected. The server’s up-link (i.e. the link to send data to the Internet) is an OC12 link, whose speed is roughly 622 Mbps. Let the server infect each of the vulnerable hosts one by one. How long does it take until all vulnerable hosts are infected?
  • Now, suppose initially a computer with an ADSL connection as above is infected. The worm writer decides to use a P2P-type of strategy for infection. The infection strategy can be visualized as a tree, whose root is the originally infected host. A parent node, upon infected, will infect each of its children one-by-one in some order. This tree has a million and one nodes. Let T(n) denote the minimum infection time of a tree with n nodes whose root is infected. We are interested in computing T(1000001).

    – Write a recursive formula for computing T(n).

    – What is T(1000001), according to your recursive formula? (You may need to write a very short piece of code to compute this. If the code is recursive, it might never terminate. Think of a way [very simple] to write an iterative one, with a for loop.)

Problem 2. Repeat the above question with a 4 GB file instead of the 404 worm bytes.

Chuyên mục: Mạng máy tính & Thuật Toán | Bình luận »

PCP 9 — Expanders: tích zig-zag

Ngô Quang Hưng | 25 tháng 06, 2009 | Bản để in Bản để in

8.j. Tích zig-zag

Chúng ta đã thấy rằng đã số các ứng dụng của expanders không những cần sự tồn tại của expanders mà còn cần thuật toán xây dựng expanders hiệu quả (hoặc tương đối cụ thể, hoặc rất cụ thể). Bài này viết về một phương pháp/thuật toán hiệu quả để xây dựng expanders một cách rất cụ thể gọi là tích zig-zag. Quan trọng hơn, phương pháp này tiềm ẩn những ý tưởng áp dụng được vào các bài toán khác, như trong chứng minh {\mathsf{L=SL}} sẽ trình bày trong bài tới, hoặc trong bản thân chứng minh định lý PCP của Dinur sẽ trình bày sau.

8.j.1. Trực quan

Tạo một expander tốt không khó khăn gì, ví dụ như {K_n} là expander tốt nhất có thể có. Nhưng tạo expander thưa, với constant degree, thì khó. Một ý tưởng tự nhiên là thử tìm cách xây dựng một expander lớn từ một số các expanders nhỏ hơn sao cho không làm tăng degree quá đáng thì ta có hy vọng. Ví dụ, một cách xây dựng expander lớn từ expander nhỏ là “bình phương” cái expander nhỏ: {\hat\lambda(G^2) = \hat\lambda^2(G)}. Cái dở là ta không thể “nhân” với {G} mãi được vì degree cũng bị bình phương luôn.

Tích zig-zag là một cách xây dựng một expander lớn từ hai expanders nhỏ hơn. Cụ thể là, cho trước {G} và {H} là {(n,m,\alpha)}-spectral expander và {(m,d,\beta)}-spectral expander, theo thứ tự. Chúng ta sẽ xây dựng một đồ thị mới, ký hiệu là {G \textcircled{z} H}, gọi là “tích zig-zag” của {G} và {H}. Tích này sẽ là một {(mn, d^2, f(\alpha,\beta))}-spectral expander, trong đó cái spectral expansion rate mới {f(\alpha, \beta)<1} nếu {\alpha<1} và {\beta<1}. Nôm na là, nếu {G} và {H} là expanders thì {G \textcircled{z} H} cũng là expander.

Ta sẽ chứng minh được rằng {f(\alpha,\beta)\leq \alpha +\beta+\beta^2} (đây là chặn trên cụ thể, còn {\alpha,\beta<1} vẫn suy ra {f(\alpha,\beta)<1} nhưng đó không phải là chặn trên cụ thể). Từ đó, nếu ta bắt đầu bằng một đồ thị {H} là {(d^4,d, 1/5)}-spectral expander (Bài tập: chứng minh tồn tại bằng phương pháp xác suất), thì ta có thể xây dựng một họ các expanders như sau:

  • {G_1 = H^2}
  • {G_2 = G_i^2 \textcircled{z} H}

Dễ thấy rằng đây là một chuỗi vô hạn các expanders. Đồ thị {G_i} là một {(d^{4i}, d^2, 2/5)}-spectral expander. Có thể cải tiến cái chặn trên {\alpha+\beta+\beta^2} được, nhưng điều đó không quan trọng. Xem thêm bài báo tích zig-zag nguyên thủy của Reingold, Vahdan, và Wigderson.

Bây giờ ta mô tả {G \textcircled{z} H}. Chú ý rằng degree của {G} bằng tổng số đỉnh của {H}. Trước hết, với mỗi đỉnh {v} của {G}, đặt tên các cạnh xung quanh {v} bằng các đỉnh của {H} một cách tùy hỉ. Xem hình dưới đây, tôi đã đặt tên các cạnh xung quanh v, u, w.

zigzag

Mỗi đỉnh của {G \textcircled{z} H} là một cặp đỉnh {(u,v) \in V(G) \times V(H)}. Có thể hình dung tập đỉnh của {G \textcircled{z} H} được chia thành {n} “đám mây”, mỗi đám mây là một nhân bản của {H} (cạnh màu xanh lá cây). Sau đó, ta nối một đỉnh của đám mây này đến một đỉnh của đám mây khác nếu đỉnh này là tên của đầu này của cạnh và đỉnh kia là tên ở đầu kia của cạnh. Ví dụ, trong hình thì ở {G} có cạnh {wv} với tên ở đầu {w} là {2} và tên ở đầu {v} là {1}, ta nối đỉnh {2} trong đám mây của {w} với đỉnh {1} trong đám mây của {v} bằng một cạnh màu đen.

Nếu ta chỉ giữ các cạnh màu xanh lá cây và cạnh màu đen, thì ta có cái gọi là “tích thay thế” (replacement product). Degree của tích thay thế là {d+1}. Ta có thể chứng minh được tích thay thế cũng là expander. Tuy nhiên, về mặt kỹ thuật sẽ tiện hơn nếu ta thêm {d} cạnh song song cho mỗi cạnh của {G}; ví dụ như sẽ có {d} cạnh song song giữa đỉnh {2} trong đám mây của {w} và đỉnh {1} trong đám mây của {v}. Kết quả là một đồ thị với degree {2d}, cũng thường được gọi là tích thay thế hoặc tích thay thế cân bằng (balanced replacement product). Bài này (SODA 2007) của Alon, Schartz, và Shapira dùng tích thay thế này để xây dựng expanders (constant degree). Phép xây dựng này của Alon et al. cũng là một combinatorial construction, nhưng nó xuất hiện 6, 7 năm sau zig-zag; ngoài ra phép zig-zag cũng đóng vai trò quan trọng trong việc phát triển trực quan cho các kết quả khác, do đó chúng ta nói về tích zig-zag.

Quay lại với xây dựng tích zig-zag: các cạnh màu xanh và cạnh màu đen không phải là các cạnh của {G \textcircled{z} H}. Nếu ta có thể đi từ một đỉnh {x} của {G \textcircled{z} H} đến một đỉnh {y} của {G \textcircled{z} H} bằng cách thăm {3} cạnh: xanh-đen-xanh, thì ta nối {x} với {y} thành một cạnh của {G \textcircled{z} H}. (Vì thế mới gọi là tích zig-zag.) Trong hình, các cạnh màu đỏ mới là các cạnh của tích {G \textcircled{z} H}. Tôi chỉ vẽ ví dụ vài cạnh màu đỏ, vẽ hết sẽ cực rối.

Như vậy, một bước ngẫu nhiên trên {G \textcircled{z} H} bao gồm một bước ngẫu nhiên màu xanh trong một “đám mây” {H}, một bước xác định (deterministic) qua một cạnh đen của {G}, và một bước ngẫu nhiên (màu xanh) khác trong đám mây bên kia của {H}. Về mặt trực quan, chúng ta phải chứng minh rằng ba bước này làm cho phân bố các đỉnh trở nên gần cân bằng (uniform) hơn. (Nhớ góc nhìn xác suất của expanders.) Mỗi một đỉnh của {G \textcircled{z} H} là một cặp đỉnh {(g, h)}, với {g} là một đỉnh của {G} và {h} là một đỉnh của {H}. Đỉnh {(g,h)} sẽ gần uniform nếu mỗi tọa độ là gần uniform và độc lập với nhau. Giả sử ta bắt đầu từ một phân bố mà phân bố của {h} (bên trong đám mây) là xa uniform (entropy thấp), thì bước ngẫu nhiên màu xanh đầu tiên sẽ làm cho phân bố của {h} gần uniform hơn vì {H} là expander. Hai bước còn lại thì một bước là xác định, và một bước ngẫu nhiên trên {H} sẽ không làm giảm độ uniform của phân bố của {h}. Còn nếu phân bố của {h} đã là uniform thì bước một bước vẫn giữ nó uniform, trong khi đó phân bố của {g} sẽ trở nên uniform hơn vì bước màu đen (cùng với bước màu xanh đầu) sẽ tương tự như một bước ngẫu nhiên trên {G}. Tuy nhiên, vì các cạnh đen thực sự là một matching của các đỉnh của {G \textcircled{z} H}, do đó nếu ta tăng entropy của (phân bố của) {g} thì sẽ làm giảm entropy của {h}. Do đó, ta cần bước màu xanh thứ {3} để tăng lại entropy của {h}. (Vì thế, bài zig-zag nguyên thủy có chữ “entropy wave” trong đó.) Chứng minh dưới đây theo trực quan này.

8.j.2. Định nghĩa cụ thể và phân tích

Với mỗi đỉnh {u \in V(G)}, đặt tên các cạnh kề với {u} theo thứ tự tùy ý là {e_u^1, \dots, e_u^m}. Đồ thị {G \textcircled{z} H} được xây dựng như sau:

  • {V(G \textcircled{z} H) = \{(u,i) \ | \ u\in V(G), i \in [m]=V(H)\}}.
  • Có một cạnh nối {(u,i)} với {(v,j)} nếu và chỉ nếu tồn tại {k, l \in [m]} sao cho {ik \in E(H)}, {e_u^k = e_v^l}, và {lj \in E{H}}.

Dễ thấy rằng {G \textcircled{z} H} có {mn} đỉnh và (regular) degree {d^2}. Gọi {\mathbf{\hat A}, \mathbf{\hat B}} là các normalized adjacency matrices của {G, H}, theo thứ tự. Định nghĩa một ma trận {mn \times mn} đặt tên là {\mathbf P} như sau: {p_{(u,k),(v,l)} = 1} nếu và chỉ nếu {e_u^k = e_v^l}. Lưu ý rằng {\mathbf P} là một ma trận hoán vị đối xứng (symmetric permutation matrix). Định nghĩa ma trận {\mathbf{\tilde B} = \mathbf I_n \otimes \mathbf{\hat B}} (trong đó {\otimes} là ký hiệu của tensor product của hai ma trận).

Bài tập: chứng minh rằng {\mathbf M = \mathbf{\tilde B P \tilde B}} chính là normalized adjacency matrix của tích zig-zag {G \textcircled{z} H}.

Từ đó, ta có

\displaystyle f(\alpha,\beta) = \max_{\mathbf{x \perp u}} \frac{|\langle \mathbf{\tilde B P \tilde B x, x} \rangle|}{\langle \mathbf{x, x} \rangle}.

Xét một vector {\mathbf{x \perp u}, \mathbf x \in \mathbb R^{mn}} tùy ý. Định nghĩa một “vector thu thập” {C(\mathbf x) \in \mathbb R^n} như sau: {C(\mathbf x)_u = \frac 1 m \sum_{i\in [m]} x_{(u,i)}}. Nói cách khác, tọa độ thứ {u} của {C(\mathbf x)} là giá trị trung bình của các tọa độ {x_{(u,i)}} trong “đám mây” thứ {u} của vector {\mathbf x}. Đến đây, định nghĩa các thành phần song song và vuông góc:

\displaystyle \mathbf x^{\|} := C(\mathbf x) \otimes \mathbf 1_m

trong đó {\mathbf 1_m \in \mathbb R^m} là vector mà tất cả các tọa độ đều bằng {1}; và,

\displaystyle \mathbf x^\perp = \mathbf x - \mathbf x^\|

Xét vector {\mathbf x \perp \mathbf u}, chúng ta muốn chứng minh rằng {|\langle \mathbf{\tilde B P \tilde B x, x} \rangle| \leq f(\alpha, \beta) \langle \mathbf{x,x} \rangle}. Hãy bắt đầu với vế trái trước. Lưu ý rằng, do {\mathbf x^\|} “phân bố đều” trên mỗi “đám mây”, ta có {\mathbf{\tilde Bx^\| = x^\|}}. (Bài tập: chứng minh điều này.)

\displaystyle |\langle \mathbf{\tilde B P \tilde B (x^\|+x^\perp), (x^\|+x^\perp)} \rangle| \leq |\langle \mathbf{Px^\|, x^\|} \rangle| + 2|\langle \mathbf{P\tilde B x^\perp, \tilde B x^\|} \rangle| + \|\mathbf{\tilde Bx^\perp} \|^2

Xét số hạng cuối cùng. Do vector {\mathbf x^\perp} “phản phân bố đều” trên mỗi “đám mây” (nghĩa là tổng của các tọa độ của {\mathbf x^\perp} trên từng đám mây là bằng {0}), ta suy ra rằng {\|\mathbf{\tilde Bx^\perp}\| \leq \beta \|\mathbf x^\perp\|}.

Kế tiếp, ta chặn số hạng thứ hai. Do {\mathbf P} là một ma trận hoán vị, nó không thay đổi norm của một vector. Ta có:

\displaystyle 2|\langle \mathbf{P\tilde B x^\perp, \tilde B x^\|} \rangle| \leq 2\| \mathbf{P\tilde Bx^\perp}\| \|\mathbf{\tilde B x^\|}\| \leq 2\beta \| {\bf x}^\perp\| \|{\bf x}^\|\|

Cuối cùng, ta chặn số hạng thứ nhất.

Bài tập: chứng minh rằng

\displaystyle \langle \mathbf{Px^\|, x^\|} \rangle = m \langle \mathbf{\hat A} C(\mathbf x), C(\mathbf x)\rangle \leq m\alpha \|C(\mathbf x)\|^2 = \alpha \|\mathbf x^\|\|^2

Vì thế,

\displaystyle |\langle \mathbf{\tilde B P \tilde B x, x} \rangle| \leq \alpha \|\mathbf x^\|\|^2 + 2\beta \| {\bf x}^\perp\| \|{\bf x}^\|\| + \beta^2 \|\mathbf x^\perp\|^2

Lưu ý rằng {\|\mathbf x\|^2 = \|\mathbf x^\|\|^2 + \|\mathbf x^\perp\|^2}. Ta suy ra

\displaystyle |\langle \mathbf{\tilde B P \tilde B x, x} \rangle| \leq \max(\alpha+\beta, \beta+\beta^2)\|\mathbf x\|^2 \leq (\alpha+\beta+\beta^2)\|\mathbf x\|^2

Như vậy, ta vừa chứng minh được định lý sau đây:

Định lý 1 (Định lý zig-zag)

Nếu {G} là một {(n,m,\alpha)}-spectral expander và {H} là một {(m,d,\beta)}-spectral expander thì tích zig-zag {G \textcircled{z} H} là một {(mn, d^2, \alpha+\beta+\beta^2)}-spectral expander.

8.j.3. Xây dựng rất cụ thể (chạy trong thời gian poly-log)

Theo như cách mô tả xây dựng họ expanders ở trên, thời gian cần để xây dựng đồ thị {G_i} là {\text{poly}(|V(G_i)|)}. Muốn một họ expanders được xây dựng một cách rất cụ thể (định nghĩa trong bài PCP 8), thì ta cần phép xây dựng này chạy trong thời gian poly-log. Ý tưởng chính là dùng phương pháp tương tự như “repeated squaring”.

Trước hết, cần định nghĩa tích tensor của hai đồ thị. Gọi {G_1=(V_1,E_1)} là một {d_1}-regular graph với {n_1} đỉnh, {G_2=(V_2,E_2)} là {d_2}-regular graph với {n_2} đỉnh. Tích tensor {G_1 \otimes G_2} được định nghĩa như sau: {V(G_1 \otimes G_2) = V_1 \times V_2}, và hai đỉnh {(u_1,u_2)} và {(v_1,v_2)} là kề nhau nếu và chỉ nếu {u_1v_1\in E_1} và {u_2v_2\in E_2}.

Bài tập: chứng minh rằng nếu {G_1} và {G_2} là {(n_1,d_1,\alpha_1)}-spectral expander và {(n_2,d_2,\alpha_2)}-spectral expander, theo thứ tự, thì {G_1 \otimes G_2} là {(n_1n_2,d_1d_2, \max(\alpha_1,\alpha_2))}-spectral expander. (Gợi ý: normalized adjacency matrix của đồ thị tích là tích tensor của hai normalized adjacency matrices.)

Từ đó, có thể xây dựng họ expanders như sau. Gọi {H} là một {(d^8,d,\alpha)}-spectral expander với các hằng số {d,\alpha<1} nào đó. Sau đó, định nghĩa

  • {G_1 = H^2}
  • {G_2 = H \otimes H}
  • {G_n = \left(G_{\left\lceil\frac{n-1}{2}\right\rceil} \otimes G_{\left\lfloor\frac{n+1}{2}\right\rfloor} \right)^2 \textcircled{z} H}, {n \geq 3}

Bài tập: chứng minh rằng, với mọi {n \geq 1}, {G_n} là một {(d^{8n}, d^2, \alpha_n)}-spectral expander trong đó {\alpha_n = \alpha + O(\alpha^2)}; và nếu cho trước một đỉnh của {G_n} thì ta có thể tính được các đỉnh kề với nó trong thời gian {\text{poly}(n) = \text{poly}(\log(|V(G_n)|))}.

Chuyên mục: Lý thuyết tính toán & Thuật Toán | Bình luận (2) »

PCP 8 — Expanders: tiết kiệm random bits và khuếch đại gap

Ngô Quang Hưng | 31 tháng 05, 2009 | Bản để in Bản để in

8.f. Sơ lược về các kết quả xây dựng một họ expanders

Định nghĩa. (Họ expanders)

Cho trước các hằng số d,\alpha>0, một chuỗi các đồ thị \{G_i\}_{i=1}^\infty là một họ (d,\alpha) của các spectral expanders nếu G_i là (n_i,d,c)-spectral expander. Trong đó, n_1<n_2 <\dots, và tồn tại một đa thức g(n) sao cho n_{i+1} = O(g(n_i)) với mọi i. Điều kiện cuối cùng này chỉ để giới hạn kích thước của các expanders trong họ. Cái sau không thể có kích thước bằng số mũ của cái trước.

Trong đa số các ứng dụng (xem dưới đây), cho trước một hằng số \alpha<1, chúng ta muốn là có một hằng số d sao cho một họ (d,\alpha) của các spectral expanders tồn tại, và mỗi thành viên trong họ có thể xây dựng được trong polynomial time.

Định nghĩa. (Họ expanders xây dựng tương đối cụ thể)

Một họ \{G_i\} của các expanders có thể xây dựng được một cách tương đối cụ thể (mildly explicit) nếu tồn tại một thuật toán mà cho input là i nó output đồ thị G_i trong thời gian \text{poly}(i).

Ví dụ: có thể xây dựng một họ các expanders như sau. Gọi n_i là số nguyên tố thứ i. Đặt V(G_i) = \mathbb Z_{n_i} (nhóm Abel). Với một đỉnh bất kỳ x \in \mathbb Z_{n_i} thì nối x với các hàng xóm x+1,x-1,x^{-1}. Trong đó, các phép tính cộng, trừ, nghịch đảo là tính trên nhóm. Và, ta định nghĩa nghịch đảo của 0 là 0. Đáng lẽ, ta có thể xây dựng đồ thị thứ i rất nhanh, nhưng vì không biết cách nào để sinh số nguyên tố thứ i ngoài cách cơ bắp (thử từng số từ 1 trở đi và dùng thuật toán AKS), cho nên tổng thời gian chạy để sinh ra đồ thị thứ i là \text{poly}(i).

Định nghĩa. (Họ expanders xây dựng rất cụ thể)

Một họ \{G_i\} của các expanders có thể xây dựng được một cách rất cụ thể (strongly explicit) nếu tồn tại một thuật toán mà cho input là i, đỉnh v \in [n_i], và số k \in [d], thuật toán in ra hàng xóm thứ k của đỉnh v trong đồ thị G_i trong thời gian \text{poly}(\log i, \log n_i, \log d) (đại khái là thời gian đa thức trong tổng số bits để biểu diễn bộ ba (i,n_i,d).

Đọc tiếp toàn bài »

Chuyên mục: Lý thuyết tính toán & Thuật Toán | Bình luận »

PCP 7 — Expanders: góc nhìn xác suất

Ngô Quang Hưng | 29 tháng 05, 2009 | Bản để in Bản để in

8.d. Spectral expanders và tốc độ hội tụ của random walks trên expanders

Trong bài này chúng ta sẽ chứng minh rằng một đồ thị có spectral gap lớn thì “tương đương” với tốc độ hội tụ của một random walk trên đồ thị càng cao. (Sở dĩ ta để tương đương trong ngoặc kép là vì một chiều chứng minh cần thay đổi đồ thị một chút.)

8.d.1. Random walk trên đồ thị d-regular, điều kiện hội tụ

Hầu hết những kết quả ta sẽ chứng minh trong đề mục này đúng cho cả các đồ thị không regular, nhưng chúng ta chỉ phát triển các kết quả trên các đồ thị d-regular cho tiện. Xét một đồ thị d-regular G với adjacency matrix \bf A. Định nghĩa \hat {\bf A} = \frac 1 d {\bf A}. Ma trận \hat {\bf A} còn được gọi là normalized adjacency matrix, và nó cũng chính là transition probability matrix của chuỗi Markov trên đồ thị G. Ở đây, chúng ta không cần biết lý thuyết về chuỗi Markov để hiểu bài này. Nếu bạn muốn biết thêm về chuỗi Markov thì tôi giới thiệu quyển Markov Chains của Norris. Về random walks trên các đồ thị thì bài này của Laci Lovasz là một bài tổng hợp tốt, và quyển sách của Doyle và Snell (miễn phí) là kinh điển, tuy hơi cũ.

Để bắt đầu một random walk trên một đồ thị thì trước hết ta chọn một đỉnh của đồ thị làm khởi điểm theo một phân bố xác suất \pi = \pi^{(0)} nào đó: \pi^{(0)}_v là xác suất mà đỉnh v là đỉnh khởi đầu. Đương nhiên 0 \leq \pi^{(0)}_v \leq 1, \forall v và \sum_v \pi^{(0)}_v = 1. Khi đang ở một đỉnh v ở bước này thì đến bước kế tiếp ta chọn ngẫu nhiên một một đỉnh kề với v (với xác suất 1/d) và “bước qua” bên đó. Gọi \pi^{(t)} là phân bố xác suất của random walk ở thời điểm t, nghĩa là \pi^{(t)}_v là xác suất mà chúng ta ở đỉnh v sau t bước. Dễ thấy rằng phân bố xác suất ở thời điểm t+1 là

\displaystyle \pi^{(t+1)} = \hat {\bf A} \pi^{(t)}.

Trong lý thuyết chuỗi Markov, phương trình trên gọi là phương trình Chapman-Kolmogorov, đơn giản là ứng dụng công thức tính conditional probability.

Đọc tiếp toàn bài »

Chuyên mục: Lý thuyết tính toán & Thuật Toán & Xác suất & thống kê | Bình luận (1) »

PCP 6 — Expanders: góc nhìn đại số

Ngô Quang Hưng | 22 tháng 05, 2009 | Bản để in Bản để in

8.c. Algebraic graph theory và spectral expansion

Để định nghĩa expanders từ góc nhìn đại số, ta cần biết một chút về algebraic graph theory và đại số tuyến tính. Về AGT thì tôi giới thiệu 2 quyển sau đây: Algebraic Graph Theory của Biggs, Spectral Graph Theory của Fan Chung. Về đại số tuyến tính thì quyển tôi thích nhất vẫn là Matrix Analysis của Horn và Johnson, kế đến là Introduction to Linear Algebra, Fourth Edition của Strang. Nếu bạn nóng lòng thì có thể đọc lecture note này của tôi cũng đủ.

Trong bài này, chúng ta sẽ chứng minh cái gọi là bất đẳng thức Cheeger-Alon-Milman. Bất đẳng thức này cho thấy sự “tương đương” của hai số đo: edge-expansion rate và spectral gap, theo nghĩa là: h(G) càng lớn thì spectral gap của G càng lớn và ngược lại.

Spectral gap là gì? Gọi \bf A là adjacency matrix của G. Do ma trận này là ma trận thực và đối xứng, nó có đủ bộ eigenvectors vuông góc nhau và các eigenvalues đều là số thực. (Xem thêm bài Trị đặc trưng và vector đặc trưng.) Gọi các eigenvalues của \bf A là \lambda_1 \geq \lambda_2 \dots \geq \lambda_n. Chúng ta cũng sẽ gọi chúng là eigenvalues của đồ thị G. Khi G là d-regular graph thì \lambda_1 = d. Spectral gap là khoảng cách giữa d và \lambda_2, nghĩa là d-\lambda_2.

Định lý Cheeger-Alon-Milman. Với mọi đồ thị d-regular G, ta có

\frac{d-\lambda_2}{2} \leq h(G) \leq \sqrt{2d(d-\lambda_2)}

Đọc tiếp toàn bài »

Chuyên mục: Lý thuyết tính toán & Thuật Toán | Bình luận (2) »

PCP 5 — Expanders: định nghĩa và góc nhìn tổ hợp

Ngô Quang Hưng | 20 tháng 05, 2009 | Bản để in Bản để in

8. Expanding graphs, còn gọi là expanders

Hôm nay chúng ta “de-tour” một chút để nói về expanders. Đã dùng một loại expander đặc biệt trong bài trước. Bây giờ cần giới thiệu kỹ hơn để dùng vào nhiều việc sau. Chắc sẽ cần ít nhất 3 bài để nói về expanders. Bài survey của S. Hoory, N. Linial , A. Wigderson trên Bulletin of the AMS là tham khảo chính trong KHMT về expanders. Bài này được giải Levi L. Conant 2008 cho exposition tốt. Có vẻ như họ đang viết một quyển sách về expander.

8.a. Trực quan

Expanders là một họ các đồ thị hữu dụng vô cùng tận trong KHMT hiện đại. Có thể nói là nhìn đâu cũng thấy expanders. Nó là cái gì ghê vậy? Về mặt trực quan, có ba cách tương đương nhau để mô tả expanders.

  1. Góc nhìn tổ hợp (combinatorial view). Một expander là một đồ thị thưa nhưng lại liên thông mạnh (sparse yet highly connected). Thường thì ta giới hạn max-degree là hằng số để lượng hóa khái niệm “thưa”. Còn “liên thông mạnh” thì đo bằng số cạnh hoặc đỉnh cần loại bỏ để cắt liên thông (disconnect) đồ thị. Nói cách khác, một expander là một đồ thị có max-degree bị chặn; và, bất kỳ một tập “nhỏ” các đỉnh nào cũng có neighborhood “lớn” (có biên giới lớn).

    Khi nhìn expander theo cách này chúng ta sẽ thấy nó nhiều ứng dụng rất tự nhiên: dùng nó để nối mạng P2P (hoặc để phân tích connectivity), để thiết kế worm propagation schemes hoặc thiết kế botnet command propagation, để thiết kế topology cho switching networks (xem bài này về WDM network, hay bài này về telephone switching networks), để chứng minh hardness of approximation như ta đã làm trong bài trước, để xây dựng error-correcting codes, vân vân.

  2. Góc nhìn xác suất (probabilistic view). Một expander là một đồ thị mà nếu ta bước ngẫu nhiên dọc theo các cạnh (take a random walk on it) thì ta sẽ tiến đến cái stationary distribution rất nhanh (rapidly mixing walks).

    Khi nhìn expander theo cách này, cũng có nhiều ứng dụng tự nhiên. Ta dùng nó để thiết kế cryptographic hash function, tiết kiệm tổng số random bits cho một thuật toán ngẫu nhiên hóa, để khuếch đại gap giữa soundness và completeness, để de-randomize, để sampling hiệu quả, để chứng minh complexity results (như kết quả lừng danh gần đây L=SL của Omer Reigngold), để chứng minh định lý PCP (theo cách của Dinur như đã nói), vân vân. Dĩ nhiên, các ứng dụng đều phần nào chuyển qua chuyển lại giữa hai góc nhìn tổ hợp và xác suất. Cho nên, phân loại ứng dụng của expanders theo góc nhìn là hơi khiên cưỡng một chút.

  3. Góc nhìn đại số (algebraic view). Một họ expanders là một họ đồ thị mà khoảng cách giữa eigenvalue lớn nhất và lớn nhì bị chặn dưới bởi một hằng số. Cái khoảng cách này còn được gọi là spectral gap của họ đồ thị này. Đại khái, spectral gap càng lớn thì tốc độ mở rộng (expand) càng lớn, tốc độ hội tụ về equilibrium của random walk càng lớn. Góc nhìn đại số cũng có các ứng dụng riêng, nhưng ứng dụng quan trọng nhất đối với chúng ta là dùng để phân tích các expanders theo hai góc nhìn kia. Ví dụ: việc xác định expansion rate của một đồ thị là NP-hard, cho nên cái expansion rate do phương pháp đại số cung cấp, dù yếu hơn expansion rate thật sự, lại rất quan trọng trong các ứng dụng.

Đọc tiếp toàn bài »

Chuyên mục: Lý thuyết tính toán & Thuật Toán | Bình luận (9) »

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

Ngô Quang Hưng | 19 tháng 05, 2009 | Bản để in Bản để in

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:

Đọc tiếp toàn bài »

Chuyên mục: Lý thuyết tính toán & Thuật Toán | Bình luận (10) »

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

Ngô Quang Hưng | 18 tháng 05, 2009 | Bản để in Bản để in

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.

Đọc tiếp toàn bài »

Chuyên mục: Lý thuyết tính toán & Thuật Toán | Bình luận (11) »

PCP 2 — ĐL PCP và NP-hardness của Gap-Max-E3SAT

Ngô Quang Hưng | 16 tháng 05, 2009 | Bản để in Bản để in

5. Các thuật toán xấp xỉ cho các bài toán NP-Hard

Một trong các cách để giải quyết một bài toán tối ưu nhưng lại bị NP-hard là thiết kế một thuật toán xấp xỉ cho nó. Đối với các bài toán này, có một trade-off về mặt bản chất giữa chất lượng lời giải và thời gian tìm ra lời giải. Nếu muốn tìm lời giải tối ưu thì ta phải dùng hơn poly-time. Nếu muốn chạy trong poly-time thì buộc phải thỏa mãn với lời giải không nhất thiết là tối ưu.

Định nghĩa: Một thuật toán chạy trong poly-time và cho ra lời giải với giá nằm trong khoảng \alpha lần giá tối ưu thì được gọi là một \alpha-approximation algorithm của bài toán đang xét. Con số \alpha gọi là approximation ratio của thuật toán.

Ví dụ 1: trong bài toán Vertex Cover, cho một đồ thị G, ta cần tìm một số ít đỉnh nhất để “cover” tất cả các cạnh. (Một đỉnh “covers” một cạnh nếu nó kề cạnh đó.) Bài toán này là NP-Hard. Một 2-approximation algorithm cho bài này có thể thiết kế như sau:

  • Tìm một maximal matching M của G. (Chú ý rằng maximal khác với maximum. Mặc dù dùng maximum cũng được. Ngoài ra M là ký hiệu tập các cạnh của matching.)
  • Output tất cả các đỉnh (có 2|M| đỉnh) của matching này.

Dĩ nhiên bất kỳ cạnh e nào của G cũng kề với một đỉnh nào đó trong matching, vì nếu không thì có thể thêm e vào matching và do đó nó không còn là maximal nữa. Một Vertex Cover bất kỳ nào cũng phải chứa ít nhất một đỉnh cho mỗi cạnh của M. Do đó, kích thước \mathsf{opt} của Vertex Cover tối ưu cũng phải ít nhất là |M|. Vì thế,

tổng số đỉnh thuật toán outputs = 2|M| \leq 2 \cdot \mathsf{opt}

Chúng ta vừa chứng minh rằng thuật toán đơn giản trên là 2-approximation algorithm cho bài Vertex Cover. Một bài toán mở rất quan trọng trong lý thuyết thuật toán xấp xỉ là có tồn tại một (2-\epsilon)-approximation algorithm cho bài toán Vertex Cover hay không? (\epsilon là một hằng số dương tùy ý!)

Đọc tiếp toàn bài »

Chuyên mục: Lý thuyết tính toán & Thuật Toán | Bình luận (13) »