Doximex.Com: Định lý PCP và sự không xấp xỉ được

Tuesday, April 7, 2009

Định lý PCP và sự không xấp xỉ được — bài 1

1. Phi lộ

Sau định lý Cook-Levin về sự tồn tại của các bài toán NP-complete (và Karp cho biết có rất nhiều các bài toán tự nhiên cũng NP-complete), thì định lý PCP là đỉnh cao thứ hai của lý thuyết tính toán. Lịch sử các kết quả dẫn đến định lý PCP cực kỳ hấp dẫn, đi từ interactive proofs, zero knowledge proof, inapproximability, đến expanders và algorithmic coding theory. Tôi sẽ không viết lại lịch sử này, mà chỉ đưa các liên kết (như trên) để các bạn tự tham khảo lấy. Tuy nhiên, tôi hy vọng rằng trong quá trình thảo luận các bài báo và ý tưởng cơ bản trong lịch sử sẽ “lộ ra” từ từ.

Chuỗi bài này có thể xem là chuỗi bài giảng bằng tiếng Việt của tôi về đề tài này. Năm qua — mùa Thu 2008 và mùa Xuân 2009 — tôi và một đồng nghiệp đã tổ chức một năm seminar về định lý này và các kỹ thuật liên quan như expanders, property testing, và hardness of approximation. Mấy năm trước tôi cũng đã làm seminars về expanders và PCP, nhưng các bài giảng đó không được đầy đủ và không liên kết chặt chẽ như lần này.

Viết các bài kiểu này bằng tiếng Việt thật sự là rất khó khăn vì nhiều từ tôi không biết dịch, và nếu cố dịch ra thì nghe chói tai và mất thời gian. Vì thế tôi sẽ để nguyên tiếng Anh và do đó các bài viết sẽ bị trộn lẫn Anh Việt. Đành chịu. Ngôn ngữ chỉ là phương tiện để truyền tải ý tưởng. “Sự trong sáng của tiếng Việt” sẽ hy sinh cho “sự minh bạch Toán Học”.

Khi phải chọn giữa trực quan và sự chính xác về mặt ký hiệu, tôi sẽ chọn trực quan, “hoa tay múa chân” thay vì ném ra một đống ký hiệu toán học.

2. Nhớ lại lớp NP

Hãy nói về NP trước. Có vài cách hiểu và định nghĩa lớp NP. Một cách nôm na nhưng khá chính xác về mặt toán học thì: NP là lớp các bài toán mà việc kiểm định lời giải có thể làm được “dễ dàng” (nghĩa là trong polynomial-time). Còn P là lớp các bài toán mà việc tìm ra lời giải cũng dễ luôn. Do đó khẳng định “P khác NP” cũng là một khẳng định rất hiển nhiên về mặt trực quan: “có những bài toán mà kiểm định lời giải ai đó cho mình thì dễ hơn việc mình tự tìm lời giải“. Bạn nghĩ, hừm, thế mà cũng có giải thưởng một triệu đô để chứng minh điều này. Sự thực là thế đấy! Điều “hiển nhiên” đó không dễ chứng minh chút nào.

Chi tiết hơn một chút, cái nhìn hiện đại về NP như sau: một decision problem $\Pi$ thuộc lớp NP nếu tồn tại một poly-time algorithm (còn nôm na gọi là verifier — dịch là công chứng viên?) thỏa mãn các điều kiện sau đây:

Verifier nhận inputs $x, \pi$ , và trả lời YES/NO. Nhiệm vụ là xác định xem là YES-instance hay NO-instance của $\Pi$ .

Nếu là YES-instance thì tồn tại “chứng minh” $\pi$ sao cho $V(x, \pi) =$ YES.

Nếu là NO-instance thì với bất kỳ “chứng minh” $\pi$ nào ta cũng có $V(x,\pi) =$ NO.

Có thể hiểu định nghĩa trên bằng một “interactive proof system” như sau: có một Prover cực kỳ hùng mạnh (về tài nguyên tính toán), và Prover muốn thuyết phục Verifier là input là YES-instance củabài toán $\Pi$ bằng cách đưa cho Verifier toàn bộ chứng minh $\pi$ . Nếu thật sự là một YES-instance thì sẽ có cách để Prover thuyết phục được Verifier. Nếu không thì bất kể chứng minh đó là gì, Verifier cũng không bị lừa.

Điều rất quan trọng cần chú ý là chúng ta không giới hạn sức mạnh của Prover nhưng chỉ cho Verifier chạy trong poly-time. Do đó, không mất tính tổng quát ta có thể giả sử rằng “chứng minh” $\pi$ chỉ có kích thước poly (|x|) , vì nếu nó có kích thước super-polynomial thì Verifier cũng chẳng kiểm tra hết trong poly-time được

Ví dụ 1: xét bài toán Vertex Cover. Input x=(G,k) bao gồm một đồ thị và một số nguyên . Câu hỏi là đồ thị này có vertex cover nào với nhiều nhất đỉnh không. Prover sẽ trình bằng chứng là một tập con các đỉnh của đồ thị. Verifier dễ dàng kiểm chứng xem $\pi$ có là một vertex cover hay không. Vì thế Vertex Cover thuộc lớp NP.

Ví dụ 2: xét bài toán Composites. Input là (biểu diễn nhị phân của) một số nguyên dương . Câu hỏi là số nguyên dương này có phải là hợp số hay không. Prover có thể đưa chứng minh là một ước số khác và khác . Vì thế Composites thuộc lớp NP. Công trình nổi tiếng của AKS còn cho ta biết nó thuộc P luôn.

Xem NPC-compendium sẽ thấy nghìn vạn bài toán thuộc lớp NP như hai ví dụ trên. Lần đầu tiên đọc định nghĩa của NP trên, có lẽ bạn sẽ thấy nó có vẻ quá rộng, chứa tất cả các bài toán (decision) thông thường. Không phải như thế. Có rất nhiều bài toán “tự nhiên” mà ta không biết có thuộc NP hay không. Tất cả các bài toán coNP-complete thuộc loại này (và ta tin rằng chúng không thuộc NP, vì nếu không thì P=NP và trời sẽ sập.)

3. Lớp PCP vào cuộc

Khi đã nhìn NP bằng góc nhìn của một interactive proof system như trên, một câu hỏi rất tự nhiên là: “nếu chúng ta thay đổi yêu cầu về Verifier một chút thì thay vì NP ta được cái gì?” Yêu cầu hiện nay với Verifier rất mạnh: nó phải xác minh được với độ tính chính xác 100% nếu cho nó bằng chứng đúng, và phải tuyệt đối không bị lừa. Ví dụ: nếu cho Verifier sai với xác suất nhỏ thì thế nào? Nếu chỉ cho Verifier dùng sub-linear space thì thế nào? Nếu chỉ cho Verifier đọc ít bits trong chứng minh $\pi$ thôi thì thế nào? Vân vân.

Đã có hàng loạt các bài báo 22 năm đổ lại đây trả lời các câu hỏi trên (xem bài này, bài này, hay quyển Computational Complexity: A Modern Approach, có nói về một tập con của các kết quả đó). Trong hơn 20 năm đó, đã có những kết quả trên cả tuyệt vời như IP=PSPACE của Shamir, và định lý PCP chúng ta sẽ chứng minh trong chuỗi bài này. Sau mấy chục năm nghiên cứu, hóa ra là có 5 tham số quan trọng mà chúng ta có thể “xê dịch” để ép Verifier. Dưới đây hãy nói về 4 tham số randomness complexity, query complexity, completeness, và soundness trước, để tham số thứ năm alphabet size đề cập đến sau.

Randomness complexity: tham số thứ nhất là tổng số random bits mà Verifier được dùng. Trong trường hợp của NP như định nghĩa ở trên thì Verifier là deterministic, nó có randomness complexity bằng 0. Nhưng nếu ta cho phép Verifier được sai lầm với một xác suất nhỏ, thì có thể cho nó vài random bits để biến nó thành một probabilistic Verifier. (Gọi là probabilistic Turing Machine cũng được.)

Query complexity: tham số thư hai là tổng số bits trong chứng minh $\pi$ mà Verifier được truy cập. Trong trường hợp của NP như định nghĩa ở trên thì Verifier truy cập toàn bộ chứng minh. Chứng minh thì có poly-size. Do đó query complexity bằng poly(n). Thế nhưng, giả sử ta cho phép Prover đưa chứng minh có exponential-size, và Verifier không đọc hết toàn bộ chứng minh mà đọc ngẫu nhiên vào một số vị trí nào đó của chứng minh thì cái query complexity là tham số quan trọng.

Định nghĩa:

Một -restricted verifier là một randomized poly-time algorithm với randomness complexity và query complexity. (Cả lẫn đều có thể phụ thuộc vào input size, không nhất thiết là hằng số.)

Cho một chứng minh $\pi$ , ta dùng $V^\pi(x)$ để ký hiệu output (YES hay NO) của verifier cho input và chứng minh $\pi$ . Đôi khi, để cho tiện, ta cũng nói “Verifier chấp nhận ” nếu output là YES, và “Verifier bác bỏ ” nếu output là NO.

Cho các tham số $0\leq s<c\leq 1$ Một bài toán $\Pi$ thuộc lớp PCP $_{c,s}[r,q]$ nếu tồn tại một -restricted verifier thỏa mãn các điều kiện sau đây:

Completeness: nếu là YES-instance thì tồn tại một chứng minh $\pi$ sao cho Prob $[V^\pi(x)= YES] \geq c$
Soundness: nếu là NO-instance thì bất kể chứng minh $\pi$ là gì đi nữa thì Prob $[V^\pi(x)= YES] \leq s$

Nếu và thì chúng ta chỉ cần viết PCP thay vì PCP $_{1,1/2}[r,q]$ .

Bài tập: chứng minh rằng NP = PCP $_{1,s}[0,poly(n)]$ với mọi s<1 .

4. Định lý PCP

Năm 2001, giải thưởng danh giá Godel được trao cho 3 bài báo mà dân trong ngành dùng initials của các tác giả để nói về chúng: AS ở FOCS 1992, ALMSS ở FOCS 1992, và FGLSS ở FOCS 1991. FGLSS chỉ cho chúng ta “liên kết” giữa PCP và hardness of approximation, còn AS+ALMSS chứng minh định lý PCP, có thể nói là định lý quan trọng ngang tầm định lý Cook-Levin.

Định lý PCP.

Tồn tại hai hằng số sao cho NP = PCP $[c_1\log n, c_2]$ .

Để đơn giản, định lý PCP thường được viết là NP = PCP $[O(\log n), O(1)]$ .

Diễn Nôm của định lý PCP: với bất kỳ một bài toán nào trong NP thì cũng tồn tại một Verifier chỉ dùng $O(\log n)$ random bits và truy cập một hằng số các bits trong chứng minh mà vẫn xác minh được lời giải của bài toán với độ tự tin cao. Định lý này cực kỳ đáng kinh ngạc (link đến bài trên tờ Nature) vì Verifier chỉ cần truy cập một hằng số các bits trong chứng minh, và hằng số này độc lập với bài toán đang xét.

Thử tưởng tượng thế này: bạn có một chứng minh của một bài toán cực kỳ nổi tiếng, Riemann hypothesis hoặc là P khác NP; nhưng chứng minh của bạn quá dài (500 trang), cần rất nhiều thời gian để verify. Định lý PCP nói rằng, nếu bạn trình bày chứng minh của bạn theo một dạng nhất định (có thể sẽ dài hơn 500 trang, nhưng có thể dùng máy tính để làm), gọi là $\pi$ , rồi bạn “đút” chứng minh này vào một chương trình tên là Verifier; thì Verifier sẽ có thể xác nhận chứng minh của bạn là đúng bằng cách truy cập cỡ khoảng vài chục từ trong $\pi$ và output YES (chứng minh đúng) hoặc NO (chứng minh sai).

Nếu chứng minh của bạn là đúng thì Verifier luôn output YES. Nếu chứng minh của bạn là sai thì Verifier output YES với xác suất nhiều nhất là 1/2. Tôi có thể chạy Verifier 100 lần độc lập, và chỉ xác nhận chứng minh của bạn nếu Verifier nói YES 100 lần liên tục. Do đó:

Nếu chứng minh Riemann hypothesis của bạn là đúng thì Verifier luôn output YES. Nếu chứng minh của bạn là sai thì Verifier output YES với xác suất nhiều nhất là $\frac{1}{2^{100}}$ . Chú ý rằng Verifier vẫn chỉ truy cập một hằng số các từ từ chứng minh của bạn.

Nếu bạn gửi chứng minh đến một journal danh tiếng nào đó, thì xác suất mà journal editors phạm lỗi trong khi đọc bài của bạn tệ hơn xác suất mà Verifier trên phạm lỗi rất nhiều. Kinh dị chưa?

Còn rất nhiều thứ làm cho định lý PCP cực kỳ … kinh dị. Ví dụ, chúng ta sẽ chứng minh các định lý sau đây:

Định lý Håstad (1997) (bài này): Với mọi hằng số $\epsilon,\delta>0$ , ta có NP = PCP $_{1-\epsilon, 1/2+\delta}[O(\log n), 3]$ .

Một bài báo sau đó của GLST (FOCS 1998) chứng minh khẳng định mạnh hơn một chút: NP = PCP $_{1, 1/2+\delta}[O(\log n), 3]$ .

Để chứng minh định lý này (và định lý PCP) chúng ta sẽ cần Fourier analysis of Boolean functions, expander graphs, property testing, và coding theory.

Điều kinh dị nhất là, có thể nói rằng P và NP chỉ cách nhau có mỗi $\delta$ nhỏ tùy ý

Định lý Karkoff-Zwick (bài này ở FOCS 97): ta có P = PCP $_{1, 1/2}[O(\log n), 3]$ .

Để chứng minh định lý này chúng ta sẽ cần biết một chút Semi-definite programming, một kỹ thuật trung tâm của optimization và approximation algorithm design.

Trong bài tới, chúng ta sẽ nói thêm về liên hệ giữa định lý PCP và hardness of approximation.

Xem đầy đủ bài viết tại http://www.procul.org/blog/2009/04/07/pcp1/