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

NQH | 07/04/2009 |

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 $V$ (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 $x$ là YES-instance hay NO-instance của $\Pi$ .
Nếu $x$ là YES-instance thì tồn tại “chứng minh” $\pi$ sao cho $V(x, \pi) =$ YES.
Nếu $x$ 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 $P$ 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 $x$ 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 $x$ 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ị $G$ và một số nguyên $k$ . Câu hỏi là đồ thị này có vertex cover nào với nhiều nhất $k$ đỉ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 $x$ là (biểu diễn nhị phân của) một số nguyên dương $m$ . 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 $1$ và khác $x$ . 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ì 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 $(r,q)$ -restricted verifier $V$ là một randomized poly-time algorithm với randomness complexity $r$ và query complexity $q$ . (Cả $r$ lẫn $q$ đề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 $x$ và chứng minh $\pi$ . Đôi khi, để cho tiện, ta cũng nói “Verifier chấp nhận $x$ ” nếu output là YES, và “Verifier bác bỏ $x$ ” 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 $(r,q)$ -restricted verifier thỏa mãn các điều kiện sau đây:

Completeness: nếu $x$ 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 $x$ 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 $c=1$ và $s=1/2$ thì chúng ta chỉ cần viết PCP $[r,q]$ 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ố $c_1, c_2$ 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.

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

60 Comments

Thang

Posted 07/04/2009 at 10:54 am | Permalink

Cảm ơn anh Hưng. Em chưa có thời gian đọc ngay, để dành để nghiền ngẫm sau nhưng scan qua đã thấy bài viết rất trực quan & interesting.

Reply
RongChoi

Posted 08/04/2009 at 5:09 am | Permalink

Cảm ơn anh Hưng về bài viết rất hay.

Em có 1 thắc mắc nhỏ liên quan đến ví dụ của anh về sự kinh dị của định lý PCP, áp dụng cho “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”.
Câu hỏi của em (có thể là rất ngớ ngẩn) là liệu 2 bài toán trên đây có thuộc lớp NP hay không? Bởi theo phần anh trình bày thì định lý PCP là cho lớp NP.

Quả thật là em chưa thấy kinh ngạc lắm (tuy đã thấy rất thú vị ) về định lý PCP. Có lẽ điều kinh dị sẽ đến bởi sự liên quan giữa định lý PCP (đi theo con đường Interactive Proof…) và Harness of approximation (một thế giới khá xa lạ so với IP).

Hiện em chưa thấy kinh dị bởi lẽ so với zero-knowledge proof (ZK) thì cũng không thấy gì kỳ lạ hơn. Cả hai đều có chung điều kỳ lạ “tôi thuyết phục anh mà anh không cần xem xét hết chứng minh của tôi”. Nếu điều lạ trong PCP là anh chỉ cần xem vài vị trí trong cái proof đó thì điều kỳ lạ trong ZK cũng không hề kém: sau khi bị thuyết phục bởi tính đúng đắn của cái proof của tôi, anh không hề có tí thông tin nào về cái proof đó.

Em không biết đã có nhiều nghiên cứu về sự liên hệ giữa ZK và PCP chưa? ZK = IP = PSPACE, trong khi hình như PCP chỉ đẹp cho NP?

Một comment nhỏ nữa là câu anh viết “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.)” không chính xác lắm. NP = co-NP chưa chắc gì đã dẫn đến P = NP, và do vậy, trời chưa chắc đã sập (chỉ có PH là sập )

Reply
Ngô Quang Hưng

Posted 08/04/2009 at 5:45 am | Permalink
Arh, cảm ơn RongChoi đã chỉ ra mấy chỗ không chính xác.

1. Đúng là lúc viết “trời sập” tôi nghĩ đến đám
```
\Sigma_i, \Pi_i
```
sập, nhưng lại cũng nghĩ đến phát biểu ngược lại là P=NP dẫn đến NP=coNP. Sẽ sửa lại cho đúng

2. Về sự kinh ngạc thì dĩ nhiên nếu chúng ta đã thấy ZK thì không thấy PCP là quá kinh dị nữa; chúng nó cùng một tinh thần. Nhưng mà như vậy cũng không công bằng với PCP lắm, vì ai thấy PCP trước rồi sẽ không thấy ZK là kinh dị nữa Hy vọng đến bài sau về liên hệ với inapproximation sẽ có những điều “kinh dị” với RongChoi hơn.

Câu hỏi của em (có thể là rất ngớ ngẩn) là liệu 2 bài toán trên đây có thuộc lớp NP hay không? Bởi theo phần anh trình bày thì định lý PCP là cho lớp NP.

3. Câu hỏi không ngớ ngẩn chút nào. Đoạn này tôi hơi sensationalize một chút. Nói cho thật sự chính xác thì có lẽ ta chỉ có thể kết luận là một bộ phận (lớn) của các phát biểu trong lý thuyết số, hoặc là các phát biểu trong lý thuyết tập hợp ZFC là thuộc NP vì đã có tiền nhân axiomatize chúng rồi. Ví dụ như P vs. NP có thể độc lập với Peano arithmetic.. Còn Riemann hypothesis thì tôi tin rằng có thể phát biểu dùng ZFC set theory.

4. Về ZK vs. IP thì để tôi xem/hỏi lại — tôi không theo dõi các nghiên cứu về IP.
Reply
Ngô Quang Hưng

Posted 08/04/2009 at 10:02 am | Permalink

@RongChoi, thêm về số (4) ở trên

Bài này có lẽ là survey gần đây nhất về ZK (+ các biến thể SZKP, CZKP, SZKA, CZKA). À, hình như chúng ta chỉ biết CZK=IP nếu giả sử tồn tại 1-way hash-functions thôi (Ben-Or et al.).

Về liên hệ giữa PCP và các lớp ZK thì tôi không thấy mấy.

Reply
RongChoi

Posted 09/04/2009 at 5:10 am | Permalink

- Đúng là ZK = IP dưới giả thiết tồn tại one-way function. Nhưng nếu giả thiết này sai thì trời gần sập (toàn bộ Crypto được xây dựng trên giả thiết này). (trong các khái niệm ZK thì computational-ZK quan trọng hơn cả nên khi ko nói tới perfect-ZK và statistical-ZK thì ta thường cZK được ký hiệu bởi ZK cho tiện).

- Ngoài ra em cũng đang cảm thấy tò mò không hiểu sao PCP lại được khởi nguồn từ Interactive proof?
Theo cách anh trình bày thì PCP khởi nguồn từ BPP thì hợp lý hơn? Hoàn toàn không có interation một cách đúng nghĩa giữa prover và verifier. Zero-knowledge ngược lại rất đặc trưng cho một interactive proof: verifier chọn và gửi câu hỏi cho prover và dựa trên câu hỏi nhận được mà prover phải trả lời cho câu hỏi đó một cách thuyết phục, đồng thời không để lộ thông tin về proof.

Anh Hưng có thể giới thiệu đôi chút về ý tưởng chứng minh định lý PCP được không ạ? Có lẽ ở đó xuất hiện rõ vai trò của Interactive proof?

- Em nghĩ kỹ hơn thì cảm thấy hai phát biểu về Riemann hypothesis và “NP=P?” không thể thuộc NP được. Lý dó là hai phát biểu này không thể được gắn với một language; input của nó là hằng số và sự giải quyết nó không phụ thuộc vào thời gian hay không gian của một máy nào đó. Có lẽ PCP không áp dụng được cho hai trường hợp này?

Reply
Ngô Quang Hưng

Posted 09/04/2009 at 9:07 am | Permalink

Hi RongChoi,

Tôi sẽ chứng minh định lý PCP trong chuỗi bài này. Khi nói thêm về hardness of approx thì RongChoi sẽ thấy PCP liên quan đến cả Multi-prover IP. PCP bắt nguồn từ bài báo là ông tổ của mọi loại interactive proof: The Knowledge Complexity of Interactive Proof Systems, của Goldwasser, Micali, and Rackoff (STOC 85). Đại khái, có 2 cách chứng minh định lý PCP. Cách một là cách của AS, ALMSS là cách đại số: mã hóa cái chứng minh bằng một error-correcting code, thiết kế Verifier cho một constraint satisfaction problem, và dùng các local tester như sub-module. Cách 2 là các của Irit Dinur hồi 2005, và là cách tôi sẽ trình bày thì mang tính combinatorial hơn. Đại khái chỉ là một reduction từ một NPC-problem. Cái reduction đó sẽ cần expanders, locally decodable codes, linearity testing (of linear codes), và một bước gap-amplification rất hay. Dùng luôn cả một ý tưởng của Reingold trong chứng minh L=SL gần đây.

Các phát biểu Riemann hypothesis hay P=NP không phải tự thân là language, mà là các inputs mà chúng ta muốn thử xem có thuộc language THEOREMS không. THEOREMs là tập hợp tất cả các mệnh đề đúng trong ZFC-set theory chẳng hạn, và do đó language này thuộc NP.

Chỉ có điều là hiện nay không ai rảnh đi viết tiếp Principia Mathematica của Russell và Whitehead, do đó không chắc lắm là viết mệnh đề P=NP hoặc Riemann hypothesis dùng ZFC-set theory hay Peano arithmetic thì (có được hay không và) tốn bao nhiêu giấy thôi.

Reply
RongChoi

Posted 10/04/2009 at 12:54 am | Permalink

Hi anh Hưng,
Rất mong được đọc các bài giới thiệu chứng minh định lý PCP của anh.

Theo em thì biểu diễn Riemann hypothesis dùng ZFC-set theory hay Peano arithmetic – đều là các lý thuyết hình thức cấp 1 – sẽ luôn xuất hiện universal quantifier, do đó, sẽ không thể được gắn với một language trong lớp NP. Em sẽ rất ngạc nhiên nếu anh có thế loại bỏ được universal quantifier trong bất kể mô hình nào. Nếu loại bỏ được thì có lẽ sẽ giải quyết được nhiều bài toán lớn như NP = coNP.

Đối với P=NP, trong ví dụ của anh, theo em (không chắc lắm ^^) P=NP sẽ phải tương đương với một phát biểu về một tính chất của language THEOREMS nào đó chứ không thể tương đương với phát biểu “kiểm tra một input có thuộc language THEOREMS hay không”.

Dù có thể sai một cách ngây thơ, em cho rằng PCP theorem sẽ không giúp được gì cho việc kiểm tra các chứng minh phức tạp trong toán học (chứng minh phức tạp theo nghĩa là một journal danh tiếng có thể phạm lỗi khi kiểm tra nó, hoặc là như anh nói, là xác suất mà journal editors phạm lỗi trong khi đọc bài chứng minh tệ hơn xác suất mà Verifier trong PCP phạm lỗi rất nhiều).

Reply
Ngô Quang Hưng

Posted 10/04/2009 at 1:14 pm | Permalink
Hi RongChoi,

1. Về universal quantifier: câu hỏi của RongChoi rất hay và dĩ nhiên không ngây thơ chút nào.

Sự xuất hiện của một universal quantifier không nhất thiết dẫn đến là phát biểu toán học đó không thuộc một lớp nào đó trong NP. Ví dụ: Hilbert’s nullstellensatz đại khái nói rằng một hệ phương trình (1) vô nghiệm nếu và chỉ nếu một phương trình (2) khác có nghiệm. [Hệ (1) bao gồm các đa thức đa biến trên một algebraically closed field, còn phương trình (2) là một phương trình đa thức. Có khá nhiều phiên bản của nullstellensatz, bao gồm cả phiên bản differential.] Do đó, để chứng minh một định lý kiểu như
Với mọi
```
x \in \mathbb F^n
```
, các đẳng thức sau đây không đúng cùng một lúc
```
F_i(x) = 0, i=1..m
```
,
thì ta chỉ cần đưa bằng chứng là một nghiệm của một phương trình đa thức khác. Nếu nghiệm này có degree nhỏ thì ta đã có một polynomial-sized proof rằng hệ phương trình trên vô nghiệm. Hướng nghiên cứu chứng minh infeasibility bằng các biến thể của nullstellensatz (gọi là nullstellensatz refutation) được dùng rất nhiều trong proof complexity. Ví dụ, xem bài survey này.

Tôi nhắc đến hai phiên bản algebraically closed field và differential nullstellensatz để muốn nói rằng tập hợp các định lý có universal quantifier mà thuộc NP là tập không tầm thường, và hoàn toàn journal referee có thể phạm lỗi khi đọc chúng. (Ngoài ra còn có combinatorial nullstellensatz của Noga Alon gần đây cực kỳ thú vị.) Terry Tao có một blog post về nullstellensatz năm ngoái, có thể google để tham khảo thêm.

2. lớp các định lý của ZFC-set theory mà có chứng minh ngắn (poly-size) tất nhiên là thuộc NP, by definition. Dĩ nhiên RongChoi nói đúng là nếu ta hiểu biết nhiều về lớp các định lý này thì gần như có thể chứng minh NP = coNP rồi. Nhưng những thứ ta biết rằng thuộc NP cũng không phải chỉ là các định lý dễ xác minh bởi con người.

3. PCP Theorem chỉ giúp kiểm tra chứng minh phức tạp trong toán học trên lý thuyết. Trên thực tế, còn nhiều vấn đề. Ví dụ như làm thế nào để tin rằng implementation của cái Verifier đó là không có bug.
Reply
RongChoi

Posted 10/04/2009 at 2:27 pm | Permalink

Hi anh Hưng,
Ví dụ của anh về Hilbert’s Nullstellensatz rất hay và như anh nói, có lẽ tập hợp các định lý có universal quantifier mà thuộc NP là tập không tầm thường. Nhưng những tập này sẽ phải được xây dựng khá một cách đặc biệt và do vậy, sẽ là rất kỳ lạ khi ngôn ngữ hình thức hoá của một bài toán lý thuyết số như Riemann hypothesis rơi trúng vào tập đặc biệt này ^^

Định lý PCP dành cho NP. Nhưng nếu đã là một bài toán thuộc NP thì tức là nó có chứng minh ngắn (poly-size). Như vậy PCP chỉ dành cho các bài toán có chứng minh dễ, vậy thì nó đâu có thể giúp gì lắm cho việc kiểm tra nhỉ? Mặt khác, do bài toán thuộc NP nên ta có thể xây dựng được một deterministic Verifier kiểm tra proof đó với độ chính xác tuyệt đối trong thời gian ngắn (poly-time). Như vậy thì journal referee chỉ cần cho chạy cái Verifier này là an tâm chứ sao phải qua PCP nhỉ?

Reply
RongChoi

Posted 10/04/2009 at 2:41 pm | Permalink

em ghi thêm 1 chút để rõ nghĩa, thay “Như vậy PCP chỉ dành cho các bài toán có chứng minh dễ” bằng Như vậy PCP chỉ dành cho các bài toán có chứng minh dễ kiểm tra”

Reply
Ngô Quang Hưng

Posted 11/04/2009 at 8:46 am | Permalink
Hello RongChoi,

Hilbert’s Nullstellensatz chỉ là một ví dụ cho thấy có những định lý không tầm thường có chứng minh ngắn, nó không phải là cách duy nhất để xây dựng chứng minh ngắn cho một mệnh đề bất kỳ trong toán học như Riemann hypothesis hay P khác NP.

Như đã nói, dùng journal referee + Riemann hypothesis làm ví dụ là tôi sensationalise kết quả lên, nhưng nó không xa sự thật theo nghĩa sau đây. PCP có thể giúp journal referee theo hai “kiểu”:

1. Một NP verifier đúng là có độ chính xác tuyệt đối trong poly-time, nhưng một PCP-verifier có độ chính xác
```
1-1/2^{100}
```
với exponential speedup, chỉ tốn thời gian tạo
```
O(\log n)
```
random bits, còn lại là làm việc trong thời gian
```
O(1)
```
. Cho dù deterministic verifier cần
```
O(n^{100})
```
-time để xác minh thì PCP-verifier vẫn chỉ cần
```
O(\log n)
```
-time thôi.

2. Định lý PCP thì nói về NP, nhưng PCP nói chung thì không chỉ nói về NP. Định lý PCP thực ra là một trong số rất nhiều các định lý về các lớp PCP khác nhau. Lý do mà nó được “tặng” cái tên định lý PCP là vì nó là định lý quan trọng nhất trong các định lý liên quan đến các lớp PCP.

Một ví dụ khác của PCP là, Babai-Fortnow-Lund 1991 chứng minh rằng MIP=NEXP = PCP[poly(n), poly(n)]. NEXP là một lớp khổng lồ. Các định lý toán học có chứng minh dài và cần exponential time để xác minh thì PCP-verifier vẫn chỉ cần polynomial time thôi. Chúng ta vẫn có exponential speedup.
Reply
RongChoi

Posted 11/04/2009 at 1:15 pm | Permalink

Hi anh Hưng,

Ta tiếp tục trao đổi về ý nghĩa của định lý PCP.

1. Về mặt lý thuyết
Em nghĩ đây là khía cạnh chúng ta đang bàn luận. Đối với em, về mặt lý thuyết, tất cả những gì làm được trong thời gian đa thức là dễ. Với định nghĩa về tính chất “dễ” như vậy, định lý PCP (cho NP) không có ý nghĩa trong việc giúp kiểm tra độ đúng đắn của một lời giải.

Định nghĩa về tính chất “dễ” theo em như vậy là phổ biến. Khi ta nói “P=NP thì trời sập” theo em cũng là trong nghĩa đó. Khi nói “P=NP toàn bộ các sơ đồ mã hoá sẽ bị phá vỡ” là trong nghĩa đó. Còn nếu ta coi đến bậc của đa thức thì “P=NP” chưa hẳn có gì sập, các sơ đồ mã hoá nếu bị phá vỡ trong thời gian đa thức n^100 sẽ vẫn rất an toàn.

2. Về exponential speedup của PCP-Verifier
2.1 PCP cho NP:

Anh cho rằng PCP-verifier chỉ tốn thời gian tạo O(\log n) random bits, còn lại là làm việc trong thời gian O(1). Em không thấy điều này. Ngoài thời gian tạo O(\log n) random bits, PCP-verifier chỉ cần truy cập O(1) bít trong proof nhưng thời gian PCP-verifier chọn O(1) bít này và thời gian PCP-verifier quyết định Accept/Reject em cho rằng vẫn là poly-time.
Theo em thấy, so với deterministic-verifier, PCP-verifier có thêm khả năng được sử dụng randomness và bị hạn chế về số lượng thông tin được truy cập vào proof. Còn lại chúng đều là poly-time machines.

2.2 PCP cho NEXP:
Như anh có giới thiệu MIP=NEXP = PCP[poly(n), poly(n)]. Như vậy có nghĩa trong multi-prover interactive proof, verifier cũng chỉ tốn có poly-time để kiểm tra proof mà thôi. Trong trường hợp này, PCP-verifier cho ta exponential speedup so với deterministic-verifier nhưng cũng chẳng hơn gì một MIP-verifier. Do vậy PCP-verifier cũng không đưa lại bước tiến gì đáng kể cho việc kiểm tra chứng minh.

3. Ý nghĩa của định lý PCP.
Em hoàn toàn đồng ý với anh ở điểm định lý PCP rất quan trọng và đẹp. Em thấy đẹp ở chỗ mọi bài toán trong NP đều tồn tại những proof mà ta chỉ cần chọn xem vài bít là đã biết nó đúng sai (theo nghĩa xác suất, tất nhiên). Điều này quả là đặc biệt và anh cũng có nói tới.
Tuy nhiên, em không đồng ý ở khoản có thể trông đợi vào PCP để kiểm tra được các chứng minh phức tạp một cách dễ dàng. Để đưa ra được một proof có tính chất đẹp như trong PCP, Prover và cả Verifier đã phải trải qua một loạt các công việc khó nhọc và phức tạp, dựa trên (về phía Prover) proof nguyên thuỷ ban đầu (mà việc kiểm tra nó không hẳn đã khó đối với deterministic-verifier hay (M)IP-verifier).

Reply
Ngô Quang Hưng

Posted 11/04/2009 at 3:46 pm | Permalink

Hi RongChoi,

Trước hết phải cảm ơn RongChoi vì tôi thấy thảo luận này rất bổ ích cho tôi. Có hai điều liên quan đến ý nghĩa của PCP tôi nghĩ chưa đủ sâu; sau thảo luận này mới nhận ra. Điểm thứ 1 là môn proof complexity còn rất “nguyên thủy” so với những gì tôi tưởng tượng (đứng ngoài nhìn vào). Điều thứ 2 liên quan đến exponential speedup như sẽ trình bày dưới đây.

Bây giờ ta hãy theo các đề mục của RongChoi ở trên:

1. Trước hết, quay lại với bài viết: tôi nói định lý PCP “kinh dị” không phải là nó giúp journal referees kiểm tra các bài báo một cách hiệu quả hơn (vì trên thực tế chẳng ai làm điều này), mà nó kinh dị là vì Verifier chỉ cần truy cập một hằng số các bits, độc lập với bài toán cần xác minh. Điều này chúng ta hoàn toàn đồng ý.

Kế đến, trong bài viết tôi “kịch tính hóa” định lý PCP bằng một phép ẩn dụ đến việc kiểm tra chứng minh Riemann hypothesis. Cái analogy này có khả năng sai ở hai chỗ: (A) là Riemann hypothesis không chắc đã thuộc về lớp nào trong NP, và (B) là cho dù nó có thuộc về một lớp của NP thì chưa chắc PCP-verifier đã chạy nhanh hơn môt NP-verifier thông thường.

Điểm (A) đã thảo luận.
Điểm (B) thì liên quan đến exponential speedup sẽ nói dưới đây.

2. Về exponential speedup

2.1. PCP cho NP

RongChoi có một quan sát rất tinh tế, là cho dù chỉ truy cập O(1)-bits từ chứng minh, Verifier có thể vẫn phải chạy trong poly-time. Điều này đúng và sai. Và đây cũng là điều lúc tôi viết về exponential speedup tôi không nghĩ tới.

Về mặt kỹ thuật, thực tế là thế này.

Có một lớp các bài toán NP-Complete gọi là constraint satisfaction problems (CSP, với O(1) constraint size) mà cái PCP-verifier cho bất ký bài toán nào trong đó cũng chỉ cần truy cập O(1)-bits từ chứng minh, làm O(1)-việc, là xong. Do đó, như tôi đã nói trong reply trước, thời gian chạy của PCP-verifier thật sự là O(log n) và chúng ta có exponential speedup. Lớp các bài toán CSP rất rộng, bao gồm các bài toán như LabelCover, MaxEkLin, MaxCut, MaxSAT, MinColoring, vân vân.

Ví dụ: Verifier của Hastad cho các bài kiểu LabelCover, MaxSAT chỉ cần lấy 3 bits a,b,c từ chứng minh, tạo một bit thứ 4 d, và kiểm tra xem a+b+c=d hay không là xong. Đó là toàn bộ công việc mà verifier làm. Do đó nó chỉ cần lấy O(log n) random bits là gần như đã hoàn tất công việc xác minh.

Nhưng RongChoi nói đúng là các bài toán khác không thuộc lớp CSP thì chưa chắc đã có verifier hiệu quả như vậy. Điều chúng ta biết là đầu tiên verifier phải “reduce” bài toán mới về một CSP problem trước (do đám CSP đều NP-Complete nên điều này hiển nhiên là làm được). Sau đó mới chạy cái Verifier hiệu quả ở trên.

Do đó, với một bài toán NP bình thường thì cần một Verifier “biên dịch” và một Verifier “xác minh”, Verifier “biên dịch” đóng vai trò dịch “định lý” đó sang Anh Văn (nghĩa là một CSP), rồi Verifier “xác minh” mới xác minh xem định lý đó đúng hay sai. Verifier “xác minh” thì có exponential speedup, nhưng verifier biên dịch thì không. Lúc tôi viết về speedup chỉ nghĩ đến Verifier xác minh mà quên Verifier biên dịch.

Như vậy, có một bài toán mở là liệu tất cả các NP-problems có đều tồn tại một O(poly log)-time PCP-verifier hay không. Tôi tin là có, và một bài báo như vậy sẽ là một đóng góp rất tốt cho PCP literature.

2.2. PCP cho NEXP

MIP = NEXP = PCP[poly, poly] được chứng minh cùng một lúc, do đó nói PCP-verifier “chẳng hơn gì” MIP-verifier thì … nói ngược lại là MIP-verifier chẳng hơn gì PCP-verifier cũng được.

3. Tôi nghĩ exponential speedup (hy sinh soundness một chút) thì hữu dụng.

Reply
RongChoi

Posted 12/04/2009 at 12:17 pm | Permalink

Hi anh Hưng,

Em cũng cảm ơn anh Hưng đã nhiệt tình thảo luận, và tạo một topic cực kỳ thú vị. Thông qua thảo luận và với cái nhìn lại, so sánh với các kết quả trước đó, em cũng hiểu được rõ hơn ý nghĩa của định lý PCP. Đến lúc này có lẽ cách nhìn về định lý này của chúng ta khá là tương đồng.

Có lẽ việc phân lớp các bài toán trong NP theo time complexity của PCP-verifier sẽ là một vấn đề thú vị.

Về PCP cho NEXP. Nếu không tính multi-prover IP thì ta cũng đã có kết quả IP=PSPACE. Và PSPACE (= NPSPACE) cũng là một lớp khổng lồ. Như vậy là đã có poly-time verifier cho lớp khổng lồ này, thậm chí là với zero-knowledge proof. Điều đó có nghĩa multi-prover IP và PCP chỉ làm mở rộng hơn cho các bài thuộc NEXP mà không thuộc NPSPACE, em chưa thấy bài toán có ý nghĩa nào thuộc lớp này.

Em đang tò mò không biết đã có định lý PCP nào cho các bài toán thông dụng mà ngoài NP (hoặc không biết có thuộc NP) hay chưa. Chẳng hạn, (zero-knowledge) interactive proof rất đơn giản cho graph non-isomorphism nhưng chưa thấy PCP cho bài toán này.

Cuối cùng, về vấn đề “liệu tất cả các NP-problems có đều tồn tại một O(poly log)-time PCP-verifier hay không” , anh tin là có, em thì lại tin là không. Kể như chúng ta đánh cược nhé. Hoặc là chúng ta sẽ giải quyết nó, hoặc chờ đợi các kết quả mới.

Chúc mọi người kỳ nghỉ Easter vui vẻ.

Reply
RongChoi

Posted 12/04/2009 at 12:24 pm | Permalink

Trong câu “Em đang tò mò không biết đã có định lý PCP nào cho các bài toán thông dụng mà ngoài NP”, ý em muốn nói đến PCP-verifier thật sự hiệu quả, nếu không là PCP[O(\log n), O(1)] thì cũng phải dạng PCP[O(\log n), O(\log n)]

Reply
DungRuoc

Posted 17/04/2009 at 12:23 am | Permalink

Xem tranh luận của anh Hưng và Rong Chơi sôi nổi nhỉ. Mặc dù nhiều phần em chưa biết nhưng cũng hóng hớt cho vui.
Nhân tiện cái ý cá độ của Rong Chơi, em cũng đồng ý với Rong Chơi là có lẽ khó có PCP-verifier sub-polynomial cho NP được.

Về thực tế, PCP languages cũng định nghĩa gần NP, chỉ là verifier chấp nhận randomness. Vậy nếu NP có PCP-verifier cho NP có độ phức tạp sub-polynomial thì nghĩa là NP có probabilistic verifier sub-poly, và thế thì gần như là các bài toán lớp P có thể tính toán gần đúng bằng Bounded Probabilistic Sub-Polynomial ?

Reply
RongChoi

Posted 17/04/2009 at 2:10 am | Permalink

Phát triển tiếp ý rất hay của DungRuoc. Giả sửa có PCP-verifier trong thời gian poly log như anh Hưng nói, thế thì verifier này cũng sẽ thuộc poly log space. Khi verifier thuộc poly log space thì một solver có thể duyệt hết space này trong khoảng thời gian sub-exponential. Điều đó có nghĩa các bài toán NP có thể giải gần đúng được trong thời gian sub-exponential, điều này rất khó xảy ra. (Hơn nữa, sau khi giải gần đúng, solver có thể chạy poly-time deterministic verifier để kiểm tra lại thật sự lời giải gần đúng có chính xác không).

Đối với lớp P có lẽ cần thận trọng hơn một chút? PCP-verifier còn có điểm khác một Verifier thông thường là có direct access vào proof, tức là dù proof có dài thì truy nhập vào một vị trí bất kỳ trong proof được coi là trực tiếp. Do vậy khi chuyển PCP-verifier sang verifier thông thường có thể phải mất thêm poly-time nếu độ dài proof là poly-size? do vậy có thể kết luận cho lớp P chưa hẳn đã đúng? (lớp NP ngược lại không bị ảnh hưởng).

Reply
RongChoi

Posted 17/04/2009 at 2:19 am | Permalink

Hình như không được. Solver phải chạy cả Prover và Verifier. Prover chạy trong poly-time chỉ với điều kiện đã có proof, còn khi tay không thì phải chạy trong thời gian không giới hạn.
Hay là RC hiểu sai ý của DungRuoc? DungRuoc giải thích rõ hơn được không?

Reply
DungRuoc

Posted 17/04/2009 at 5:17 am | Permalink

RongChoi nói đúng. Cái này còn liên quan độ dài thực của cái proof mà P đưa cho V trong PCP.

Em nêu ý trên là dựa vào hình ảnh về cái Verifier cho NP trong PCP mà anh Hưng nêu lên:

1 – Có Verifier “biên dịch” cái proof (poly) của NP, rồi có Verifier “kiểm tra” nó.

Tất cả mất Sub-Poly thì đúng là khó như em nghĩ ở trên. Nghĩa là P gần như là sub-poly BP. Cái này có vẻ cũng không giúp đưa NP về sub-expo, vì nó chỉ giúp tăng tốc việc verify, còn vẫn phải duyệt hết expo cái proofs của NP.

Nhưng liệu ý tưởng của V-”biên dịch” như anh Hưng nói đến có cần thiết không vì ta có thể ném phần này cho Prover:

2 – Các bài toàn NP thực ra được biên dịch ở Prover, rồi ném một cái chứng minh (có thể dài exponential) cho Verifier và anh này chỉ dùng O(log) random bits và truy nhập một hằng số bit trong proof.

Em nghĩ phần tiếp theo về PCP của anh Hưng sẽ làm rõ phần này. Em thì tin vào trường hợp 2 nhiều hơn. Theo em nghĩ một Verifier thì đúng là chỉ “kiểm tra” thôi. Công việc thực sự biên dịch cái proof NP thành proof PCP là của Prover. Trong trường hợp này thì độ phức tạp của Verifier có gì hay không, vì thực sự cũng phải làm trên cái proof dài ?

Reply
Ngô Quang Hưng

Posted 17/04/2009 at 5:40 am | Permalink

Hi DungDuoc, RongChoi,

Đang bận một chút chỉ nói nhoáng 1 câu rồi đi.

DungDuoc nói chính xác là không “cần” Verifier biên dịch nếu chúng ta thiết kế Verifier xác minh tốt hơn, và yêu cầu prover cung cấp nhiều “thông tin” hơn, mã hóa cái proof hay hơn. Hiện nay chúng ta chỉ biết “xác minh trực tiếp” các bài CSP (và có lẽ một vài bài đơn lẻ khác).

Một ý tưởng là sẽ bắt prover cung cấp cái execution encoding của Non-deterministic Turing Machine dùng để nhận dạng language nọ. Hồi xưa Cook dùng cái execution configuration này và “encode” nó bằng CNF formula. Mà chúng ta biết với SAT thì Verifier có thể xác minh trong O(log n) time.

Đó là lý do tại sao tôi tin là mọi ngôn ngữ trong NP đều có Verifier hiệu quả. Khi nào rảnh sẽ ngồi làm thử.

Reply
RongChoi

Posted 20/04/2009 at 8:41 am | Permalink

Hi anh Hưng,
Em cho rằng đối với SAT thì có verfier với độ phức tạp O(log n) time khi tính n là độ dài của formula. Khi tính theo số biến thì độ phức tạp ít ra là linear. Khi anh chuyển một bài toán NP về SAT thì số biến xuất hiện ít nhất bằng độ dài của input trong bài toán nguyên thuỷ, và do vậy độ phức tạp của Verifier khó có thể là poly log được.
Để có thể có Verifier với độ phức tạp poly log, em lại cho rằng anh phải có một phương pháp hoàn toàn mới chứ không dựa trên reduction “à la Cook”.

Reply
RongChoi

Posted 20/04/2009 at 12:51 pm | Permalink

Hi anh Hưng, DungRuoc

RongChoi tìm quanh và thấy khá lạ là các bài về PCP rất ít đề cập đến time complexity của verifier. Nhưng cuối cùng cũng tìm được một bài nói về vấn đề ta bàn luận. Đó là bài “Probabilistic Proof Systems: A Primer” của Oded Goldreich :
http://www.wisdom.weizmann.ac.il/~oded/pps-primer.html

Rất hay là vấn đề ta bàn luận cũng được xem là thú vị. Ở trang 58 ông viết:
“The vision of speeding-up the veriﬁcation of mundane proofs is exciting, where these proofs may refer to mundane assertions such as the correctness of a speciﬁc computation. Enabling such a speed-up requires a strength-ening of the PCP Theorem such that it mandates eﬃcient veriﬁcation time rather than “merely” low query-complexity of the veriﬁcation task. Such a strengthening is possible.”

Và định lý sau đó nói về “Stronger forms of PCP systems for NP”.
“Theorem 3.10 (Theorem 3.3 – strengthened): Every set S in NP has a PCP system V of logarithmic randomness-complexity, constant query-complexity, and quadratic time-complexity…”

Như vậy với PCP-verifier tốt nhất hiện nay có quadratic time-complexity.

Tuy nhiên, nếu cho phép relaxe đôi chút yêu cầu về PCP-verifier thì có thể có polylogarithmic time-complexity như anh Hưng nói. Ở cuối trang 59 ông viết:
“We mention that every set in N P has a PCP of proximity of logarithmic randomness-complexity, constant query-complexity, and polylogarithmic time-complexity.”

Tuy là về PCP of proximity, điều này cũng rất là thú vị.

Ngoài ra, về câu hỏi em đặt ra liệu có PCP-verifier hiệu quả cho graph non-isomorphism thì gần như là không thể. NP = PCP (log, O(1)) nhưng cũng bằng cả PCP (log, poly) nên chừng nào chưa chứng minh được graph non-isomorphism trong NP thì không thể có PCP hiệu quả cho bài toán này. Điều này cũng là thú vị, nó phần nào chỉ ra một trường hợp hạn chế của PCP so với interactive proof: trong khi IP rất hiệu quả cho graph non-isomorphism thì, dưới giả thiết NP khác co-NP, không thể có PCP-verifier hiệu quả (ít ra là không thể có PCP (log, poly)) cho bài toán này.

Chúc anh Hưng đi hội nghị vui vẻ, tuần sau em cũng đi hội nghị 1 tuần. Hẹn sau đó có dịp trao đổi tiếp. Nhờ bài dẫn nhập này và do thiếu kiên nhẫn chờ đợi, em đã đọc được kha khá về 2 cách chứng minh định lý PCP rồi ạ.

Reply
Ngô Quang Hưng

Posted 14/05/2009 at 6:13 am | Permalink

Hi RongChoi (reply to #21)

Em cho rằng đối với SAT thì có verfier với độ phức tạp O(log n) time khi tính n là độ dài của formula. Khi tính theo số biến thì độ phức tạp ít ra là linear.

Log n trong đó n là input length. n dĩ nhiên là lớn hơn tổng số biến vì tổng số biến là một phần của input.

Reply
RongChoi

Posted 14/05/2009 at 8:34 am | Permalink

Hi anh Hưng,
Tất nhiên là em biết phân biệt giữa input length và số biến: input length có thể lớn hơn rất nhiều so với số biến.
Việc nghiên cứu PCP cho SAT theo số biến chứ không theo input length cũng là một vấn đề thú vị, và em đọc được là việc thiêt kế PCP cho SAT có proof với độ dài poly(k) (k là số biến) vần là một open problem.

Ý em trong post #21 là muốn thuyết phục anh là khó có thể có log-time PCP verifier cho mọi bài toán NP. Để có điều đó, em cho rằng dù theo anh nói trong post #20 là có SAT verifier với O(log n) time, nhưng khi tính theo số biến thì SAT verifier phải có ít ra linear time complexity. Sau đó, để qui dẫn một bài toán A (trong NP) về SAT thì số biến của SAT phải chí ít bằng input length của A. Do vậy verifier cho bài toán A ít ra phải là linear time complexity (nếu thông qua qui dẫn về SAT).

Ngoài ra, em tìm được một bài báo có vẻ rất đáng đọc là “Interacrive PCP” (em mới chỉ xem qua) http://www.cc.gatech.edu/~yael/pipcp.pdf.
Dù là mở rộng tự nhiên của khái niệm PCP, nhưng nó đem lại kết quả mới cho zero-knowledge proof, có lẽ sẽ làm em thoả mãn phần nào tò mò nêu phía trên về sự liên hệ giữa PCP và ZK.

Reply
Ngô Quang Hưng

Posted 14/05/2009 at 8:54 am | Permalink

Hi RongChoi, trong bài PCP #2 (tối nay định viết sau khi nộp điểm cho học kỳ này xong), RongChoi sẽ thấy một PCP-verifier cho MaxSAT và một số bài khác.

Ý tưởng tôi nghĩ đến trong #20 là chúng ta không cần reduce bài toán về SAT, chỉ “giả lập” cái reduction này thôi. Nếu reduce thật sự thì không còn combine Verifier biên dịch và Verifier xác minh được nữa.

Reply
RongChoi

Posted 14/05/2009 at 9:16 am | Permalink

Hi anh Hưng,
OK, mong sớm đọc bài PCP#2 của anh. Bên anh kết thúc học kỳ sớm quá nhỉ.
RC

Reply
Thinh Nguyen

Posted 24/05/2009 at 8:33 pm | Permalink

Em thay co 2 diem can xem xet them o day:

1. ZFC axiom system có verifier nào để kiểm chứng proof $\pi$ của phát biểu $\phi$ trong thời gian $poly(|\pi|)$ hay không. Với các hệ tiên đề đơn giản hơn thì chắc là tồn tại, nhưng với ZFC em không rõ.

2. Giả sử $A$ là một axiom system thoả mãn điều kiện 1 thì ngôn ngữ sau đây thuộc lớp NP: L={< $\phi,1^n$ >: $\phi$ có proof trong $A$ với length $\leq n$ }

Vấn đề liên quan đến logic, set và proof theory em hầu như chẳng biết gì cả

Reply
RongChoi

Posted 28/05/2009 at 9:49 am | Permalink

Hi anh Hưng,
RC muốn quay lại chủ đề về việc áp dụng PCP cho các chứng minh của các định lý toán học.

RC bảo lưu một quan điểm cũ phía trên là những phát biểu về Riemann hypothesis, “NP=P” chẳng thể gắn với việc xét lớp cho 1 ngôn ngữ nào cả. Nhưng kết luận lần này lại khác và cho trường hợp tổng quát: mọi định lý toán học đều có thể biểu diễn được dưới dạng PCP.

Để đơn giản trong biểu diễn và hình dung, ta lấy định lý Fermat lớn làm ví dụ.
$\forall n>2, \forall \alpha,\beta,\gamma : \alpha^n+\beta^n \neq \gamma^n$

Trước tiên thử biểu diễn định lý này qua một ngôn ngữ theo cách chúng ta đã bàn luận (để xem nó có thuộc NP hay không).
Gọi $\mathcal L$ là ngôn ngữ “Fermat” được định nghĩa như sau:
Một từ $x \in \{0,1\}^\star$ thuộc $\mathcal L$ nếu và chỉ nếu:
$\forall \alpha,\beta,\gamma \in \{0,1\}^{poly(|x|)} : V(x,\alpha,\beta,\gamma)=1$
trong đó $V(x,\alpha,\beta,\gamma) := (\alpha^{|x|} + \beta^{|x|} \neq \gamma^{|x|})$
Do tân từ $V(x,\alpha,\beta,\gamma)$ tính được trong thời gian đa thức theo $|x|$ – độ dài của $x$ , theo định nghĩa về Polynomial-time Hierarchy, $\mathcal L$ thuộc $\Pi^p_1$ .

(Nôm na, $n$ trong định lý Fermat được biểu diễn bởi độ dài của $x$ .)

Một cách tương tự (tuy hơi lằng nhằng hơn một chút), ta có thể cho tương ứng Riemann hypothesis với một ngôn ngữ trong $\Pi^p_1$ .

Tóm tắt lại các phần bàn luận liên quan phía trên, chúng ta xem xét vấn đề liệu $\mathcal L$ có thể thuộc NP hay không.

Tuy nhiên, điều chúng ta bàn luận xem ra không có ý nghĩa. Định lý Fermat (và một cách tương tự cho các định lý khác) không gắn với việc $\mathcal L$ thuộc lớp nào mà tương đương với mệnh đề:

$\forall x \in \{0,1\}^\star, x\in \mathcal L$

Và khi định lý Fermat được chứng minh (ta gọi chứng minh là $W$ , dù $W$ có thể rất dài thì cũng chỉ có độ dài là constant), thì đồng thời ta cũng có thể thấy $\mathcal L$ thuộc lớp các bài toán giải được trong thời gian constant: quyết định $x\in \mathcal L$ là dễ, bởi câu trả lời luôn là “đúng” với witness là $W$ , thời gian kiểm thử phụ thuộc $W$ chứ không phụ thuộc vào độ dài của $x$ .

Hay nói tóm lại, mọi chứng minh định lý, dù phức tạp đến mấy, cũng là cách để chứng tỏ một mệnh đề là hằng đúng. Như thế, một định lý không gắn với việc 1 ngôn ngữ thuộc lớp nào, mà gắn với 1 mệnh đề hằng đúng. Các chứng minh này có độ dài O(1), việc kiểm thử chỉ phụ thuộc vào cái chứng minh mà không liên quan đến các tham số nào khác, do vậy thời gian kiểm thử cũng là O(1). Mà như thế thì các định lý sẽ luôn biểu diễn được dưới dạng PCP (tất nhiên trừ các định lý về các mệnh đề “siêu toán” mà việc biểu diễn mệnh đề đó không thể thực hiện được trong ngôn ngữ của Toán đang xét).

Reply
Thinh Nguyen

Posted 31/05/2009 at 4:59 pm | Permalink

Hi anh Hung, RC huynh,

Em van thay rat hung thu voi PCP1, vi 3 bai gan day em chi cam nhan (feel) duoc chu khong hap thu (absorb) duoc.

Em co mot cau hoi tuong doi ngoai le mot chut: tai sao trong certificate-based definition cua NL (tuong tu nhu dinh nghia cua NP) lai phai them dieu kien “read-once” nghia la chi cho phep DTM cua ta doc certificate mot lan duy nhat tu trai sang phai. Co ve nhu trong truong hop cua NP thi read-once hay khong deu nhu nhau ca vi resource cua DTM lon.

Thinh

Reply
Ngô Quang Hưng

Posted 08/07/2009 at 9:20 am | Permalink

Hello RongChoi,

Mới có bài mới ở FOCS 2009 phần nào address vấn đề time-efficiency của PCP-verifier cho NEXP. Xem định lý 1.1 và 1.2 ở đây:

http://www.wisdom.weizmann.ac.il/~orm/papers/efficient_pcps_overview.pdf

Sẽ quay lại với bình luận [May 28, 2009 at 9:49 am] vào cuối tuần tới. Đang tổ chức hội nghị nên cực bận, quên mất bình luận này của RongChoi.

Reply