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

RongChoi

Posted 08/07/2009 at 1:21 pm | Permalink

Hi anh Hưng,

Trong post [April 20, 2009 at 12:51 pm] RC trích bài của Goldreich: “We mention that every set in NP has a PCP of proximity of logarithmic randomness-complexity, constant query-complexity, and polylogarithmic time-complexity.”
RC nghĩ đây chính là Theorem 1.2 trong bài ở FOCS09 trên.

Như vậy kết quả cũng không có gì mới (chỉ xét về phương diện hiệu quả của verifier tốt nhất cho NP) thì phải. Cái mới có lẽ đến từ khía cạnh khác, khi cho thấy chứng minh theo phương pháp combinatoric có hiệu quả không thua kém gì theo phương pháp algebraic.
RC.

Reply
RongChoi

Posted 23/08/2009 at 1:47 pm | Permalink

Không biết đã có nghiên cứu về “chứng minh PCP dởm ” chưa nhỉ, RC tìm quanh chưa thấy. Ý tưởng như sau:

Giả sử ta có một công thức S = C1 and … and Ci and…and Ck và một chứng minh PCP tương ứng WPCP(S). Giả sử tồn tại poly-log time PCP-verifier V cho SAT (theo ý anh Hưng là tồn tại) , để khi S thoả được thì V(S,WPCP(S)) = 1 (tức V chấp nhận WPCP(S) như là một chứng minh S thoả được).

Bây giờ ta xét công thức S’ như sau: Chọn ngẫu nhiên 1 clause Ci của S; đảo chiều Ci (C’i = \neg Ci) trong S,; và giữ nguyên các phần còn lại để nhận được S’.

Ta tuyên bố S’ là thoả được và cung cấp chứng minh WPCP(S). Do chạy trong poly-log time, PCP-verifier V chỉ có thể phân biệt S với S’ với xác suất nhỏ. Và do vậy, với xác suất lớn, V(S’,WPCP(S)) = 1 (V chấp nhận WPCP(S) như là một chứng minh S’ thoả được). Trong khi đó nó hẳn nhiên WPCP(S) là một chứng minh sai cho S’ (không thể có cùng một phép gản thoả được cả S và S’).

Reply
Ngô Quang Hưng

Posted 23/08/2009 at 6:18 pm | Permalink

Hi RongChoi,

1. Tôi đã tìm ra một số hệ thống verify chứng minh định lý toán trên thực tế. Đang định viết một bài để trả lời câu hỏi [May 28, 2009 at 9:49 am] của RongChoi và câu hỏi [May 31, 2009 at 4:59 pm] của ThinhNguyen một thể.

2. Nếu RC đọc lại định nghĩa PCP sẽ thấy là verifier không thể lừa prover theo kiểu RC nghĩ được. Định lý PCP “amazing” ở chỗ là bất kể cái chứng minh dỏm “gần” chứng minh thật thế nào thì soundness cũng bị chặn trên bởi một hằng số (1/2 chẳng hạn). Tại vì verifier sẽ mong đợi một “encoding” của cái truth-assignment (nếu có) mà cái encoding này sẽ “khuếch tán” cái sự khác nhau rất bé (C_i thành C’_i đó) ra toàn bộ cái chứng minh. Thuật ngữ chuyên môn gọi là “gap-amplification”. Khi nào tôi viết đến chứng minh định lý RC sẽ thấy cái này rõ hơn.

Câu hỏi của RC vẫn hợp lệ theo nghĩa khác: một perturbation của công thức thì ảnh hưởng như thế nào đến soundness (cho dù vẫn bị chặn bởi 1/2, nhưng có lẽ gần 1/2 hơn chăng?).

Reply
Algorithmic Lowerboundsmen

Posted 23/08/2009 at 7:57 pm | Permalink

Hi anh Hưng, RC huynh,

0. Rất mong chờ bài viết của anh Hưng về formal proof verifier. Theo em, có lẽ ta nên tập trung vào:
–Các thuật toán của ATM (automated theorem proving) (mặc dù cái này hiện nay chỉ hữu dụng trên một số “arguably narrow areas”), và,
–Các thuật toán của practical verifiers (hiện đang phát triển tương đối nhanh bởi một số nhóm ở Europe và US). Và không có “clear cut” giữa hai khái niệm này.

Thêm nữa, proof theory và proof complexity là hai areas khác nhau, không rõ anh Hưng muốn tập trung vào cái nào.

1. Về vấn đề formal proof và mathematical logic, em có một câu hỏi nhỏ như sau:
Theo Godel, (i) một first-order theory nếu consistent thì sẽ có model, (ii) nếu ZF consistent thì Con(ZF) không thể provable một cách nội tại trong ZF, (ở đây Con(T) là first-order sentence biểu diễn consistency của T).

Như vậy, ZF + –Con(ZF) vẫn consistent và sẽ có một model. Vậy model này là gì (liệu có phải vẫn là “von Neuman universe”).
(Câu hỏi này phát sinh khi em đọc bài “Is Pvs.NP formally independent?” của S. Aaronson theo reference trong bài “Chung qui chỉ tại Cantor” của anh Hưng).

2. PCP hiện nay đã có efficient combinatorial construction cho verifier của Or Meir. Trong khi đó với algebraic method, [MR08]
đã xây dựng được 2-query PCP (có lẽ họ hướng đến UGC chăng) với almost-linear proof. Vậy các PCP courses sắp tới, chắc sẽ phải adapt nhiều thứ.

Best,
AL

Reply
RongChoi

Posted 23/08/2009 at 11:09 pm | Permalink

Anh Hưng có lẽ không để ý là RC đang giới hạn chỉ xét poly-log time verifier (là vấn đề chúng ta đang xem xét). RC tất nhiên không có ý phản bác các định lý PCP, ở đó verifier chạy trong poly time.

Hi AL, AL có thể nói rõ hơn vì sao ZF + –Con(ZF) vẫn consistent không?

Reply
ThinhNguyen

Posted 23/08/2009 at 11:56 pm | Permalink

Hi RC huynh,

1. Em cũng mới làm quen với lĩnh vực logic toán. Em nghĩ ta có thể chứng minh $ZF + -Con(ZF)$ consistent như sau:
Theo định lý bất toàn của Godel, mọi first-order thy đủ sức express Peano arithmetic thì sẽ không thể tự chứng minh consistency của bản thân (tất nhiên với enumerably enumerable axioms and axiom schema). ZF đủ sức làm điều này nên nó không thể tự chứng minh được Con(ZF) hay –Con(ZF). Vì thế việc đưa thêm –Con(ZF) vào không thể làm xuất hiện contradiction vì nếu không thì ta thu được proof by contradiction cho Con(ZF) mất rồi. Vậy là ZF + –Con(ZF) valid theo nghĩa syntactically (không thể dùng các “luật cơ bắp” để suy ra contradiction được), lại theo Godel thì đối với first-order logic thì syntactically valid và semantically valid là một.

Trong chứng minh trên, em có tham khảo bài viết của anh Hưng về định lý của Godel (và comment của RC huynh trong đó nữa).

2. Về vấn đề, weak verifier of NP, em có một số tóm tắt như sau:
Theo Cook-Levin thm thì mọi NP-language đếu có log-space verifier luôn.
Như vậy PCP verifier vẫn chưa thể nói là hoàn toàn hiệu quả hơn verifier thuở ban đầu về mặt space (tất nhiên nếu L=P thì xong luôn). Đó là chưa kể PCP có random oracle access vào proof trong khi verifier ban đầu không cần (kể cả NP lẫn NL). Việc read-once cũng không matter đối với NP, nhưng đối với NL thì read-once hay không là một giả thuyết vì nếu nó thực sự cần thiết thì $NL \neq NP$ . Còn về poly-log space mà anh đang đề cập, em chưa có idea gì cả

3. Em có nghe nói là PH chắc chắn sẽ collapse nếu một số widely-believed cryptographic assumptions là đúng.

Best,
Thinh

Reply
RongChoi

Posted 24/08/2009 at 5:10 am | Permalink

Hi Thinh,

Mình không hiểu mục đích của việc xây dựng một lý thuyết rồi khuyến mại cho thêm vào nó một tiên đề “lý thuyết của tôi không consistent”
Btw, làm thế nào để chứng minh hoặc phủ định Con(ZF + –Con(ZF))?

Về NL thì Thịnh nói đúng, certificate-based definition của NL nếu bỏ điều kiện read-once thì sẽ cho ta NP.
RC

Reply
Ngô Quang Hưng

Posted 24/08/2009 at 6:14 am | Permalink

Hi RongChoi,

Verifier cho bài max-3sat là chạy trong poly-log time đấy chứ. Không “lừa” được verifier này bằng các thay đổi cục bộ đâu.

Reply
RongChoi

Posted 24/08/2009 at 6:49 am | Permalink

Anh Hưng ơi, input có k clauses, verifier chỉ có thời gian poly-log thì làm sao đọc hết input (đọc được có tối đa poly-log(k) clauses, tức một phần rất nhỏ) mà phân biệt được S với S’ ạ? Khi không đả động đến clause bị biến đổi (Ci) thì quá trình kiểm thử chứng minh WPCP(S) của verifier cho S và cho S’ là hoàn toàn như nhau, bất kể WPCP(S) được xây dựng bằng kỹ thuật gì.
RC không nói nếu S thoả được thì S’ không thoả được, nhưng rõ ràng một chứng minh cho tính thoả được của S là một chứng minh sai cho tính thoả được của S’, và poly-log time Verifier bị lừa chấp nhận một chứng minh sai (dù điều sau này không nhất thiết dẫn đến sụ phủ định Completeness hay Soundness trong định nghĩa PCP).

Như vậy, nếu có poly-log time verifier, thì ta có thể đưa một định lý không biết đúng hay sai, nhưng có thể đưa ra một chứng minh chắc chắn sai cho định lý đó mà chú poly-log time verifier vẫn gật gù tấm tắc khen là đúng quá

Reply
Ngô Quang Hưng

Posted 24/08/2009 at 7:03 am | Permalink

Hi RC,

Định nghĩa của soundness là: với mọi chứng minh $\pi$ thì xác suất mà verifier chấp nhận một công thức không thỏa được là nhỏ hơn $1/100$ . Vấn đề là verifier không cần phải phân biệt S với S’, mà chỉ cần xác minh xem S’ có thỏa được hay không mà thôi.

Ngoài ra, technically “đổi C_i thành NOT C_i” mà viêt lại dưới dạng 3-CNF thì phải đổi công thức (thêm clauses), do đó hai chứng minh sẽ khác nhau, không dùng chứng minh này cho chứng minh kia được. Có lẽ RC phải tìm cách khác để “locally perturb” cái công thức S sao cho S’ không thỏa được.

Reply
ThinhNguyen

Posted 24/08/2009 at 7:41 am | Permalink

Dear all,

@RC huynh:
Tiếp tục về math logic: vấn đề của Con(ZF + –Con(ZF)) cũng tương tự, mặc dù ở comment trên TN đã chứng minh nó nhưng đó là chứng minh ở trong metamath (RC huynh đã có lần quảng cáo về khái niệm này ở một trong những comment ở trên nữa ) Trên thực tế, chúng chỉ là những first-order sentence nên ta lại có Con( (ZF + –Con(ZF)) + –Con(ZF + –Con(ZF)) ). TN sẽ thỉnh giáo thêm một số logicians huynh đệ về đề tài hấp dẫn này

Lại verifier: TN nghe nói holographic proof có verifier chạy trong poly-log time như RC huynh kỳ vọng. Với random-access mechanism, Verifier của nó chạy trong poly-log time ngon lành. Em chưa đọc paper [BFLS] giới thiệu holo proof. PCP proof thì poly-time constructible từ certificate nguyên thủy cho NP. Em không rõ với holo proof thì thế nào.

Email của anh ở Paris 8 hình như đã thay đổi, Gmail báo lỗi delivery (từ dạo PCP 1, 2). Đợt đó em send vài cái chắc anh đều không receive được.

@anh Hưng:
Vấn đề “read-once” có cần thiết hay không như vậy là đã rơi vào ngõ cụt vì đến nay vẫn có khả năng thậm chí $L=NP$ . Nhưng em lại có một câu hỏi khác về definition của NP-completeness.

Vấn đề em đang suy nghĩ là, NP-C theo nghĩa poly-time và log-space có khác nhau hay không đang là giả thuyết nên ta không bàn nhiều. Em đang xem xét reduction trong chứng minh của Cook-Levin Thm. Việc xây dựng lại nó trong log-space là đơn giản. Như vậy SAT là NP-C theo nghĩa log-space. Chắc các bài NP-C hiện tại cũng vậy nên mới có “giả thuyết” kia.

Ta xét việc rút gọn công thức thu được để nó chỉ còn có các ẩn là các choices của branch dẫn đến accept. Với poly-time thì việc rút gọn này cũng đơn giản. Nhưng muốn làm trong log-space thì có vẻ khó. Ít nhất cũng khó hình dung cách làm. Em quan tâm đến nó vì đây là công thức gọn nhất có thể. Công thức trong các textbook bao gồm các ô của tableau nên rất cồng kềnh nhưng vì mục tiêu chỉ là poly-time nên như vậy là đủ.

Một cách ngắn gọn, có vẻ như với log-space reduction thì certificate thu được cồng kềnh hơn so với poly-time reduction (nếu $L \neq P$ ).

Anh đang có dự định trả lời comment của RC huynh và TN trong cùng một post nên em suggest thêm vấn đề này.

Reply
RongChoi

Posted 24/08/2009 at 8:29 am | Permalink

Hi anh Hưng,

Một vấn đề hay nảy sinh là bài toán từ một công thức thoả được S, tìm cách biển đổi tối thiểu S thành S’ để nó không thoả được (ta có thể cho một độ đo hợp lý giữa 2 công thúc). Chắc cái này đã có người làm rồi.

Vấn đề của RC đơn giản hơn, đảo 1 clause bất kỳ, cái giá phải trả là không biết S’ có còn thoả được hay không.

Mệnh đề của RC rất giản đơn thôi, ghi lại từ phía trên “nếu có PCP poly-log time verifier, thì ta có thể đưa một định lý không biết đúng hay sai (cf. thằng S’) và một chứng minh chắc chắn sai cho định lý đó mà chú PCP poly-log time verifier vẫn gật gù tấm tắc khen là đúng quá “.

Tuy rất hiên nhiên nhưng cứ ghi lại chứng minh:

OK, technically, khi thay Ci bởi not Ci (trong 3SAT) thì tối đa cần dùng 3 clauses, ta có thể thêm cho S hai dummy clauses để chúng có cùng dạng, tức là tỉ lệ khác giữa S và S’ là 3/k (với k rất lớn).

Verifier là một algorithm V, với input là đầu bài+chứng minh, output là 1 hoặc 0. Xét 2 thế giới mà ta nhúng V vào
TG 1: Input là S, WPCP(S)
TG 2: Input là S’, WPCP(S)

Khi chạy, V đọc tối đa poly-log bits trên input (vì nó chạy trong poly-log time), và do vậy tối đa động đến poly-log(k) clauses.
Khi không đến 3 clauses khác nhau giữa S và S’ thì thông tin V nhận được là như nhau. Với thông tin như nhau thì output phải như nhau (xác suất “output=1″ trong hai TG1,TG2 chỉ có thể khác nhau epsilon =(poly-log(k)/k) ~ 0) (RC dùng cách nói V không phân biệt được S, S’ là để chứng minh output của V là như nhau trong 2 thế giới, chứ tất nhiên V không có nhiệm vụ đi phân biệt chúng làm gì).

Anh Hưng có đồng ý với mệnh đề này không ạ? nếu đồng ý thì RC cho rằng, dù không thật ảnh hưởng đến soundness, anh Hưng cũng thấy điều gì đó bất ổn với tụi poly-log time verifier.

Reply
Ngô Quang Hưng

Posted 24/08/2009 at 11:18 am | Permalink

Hi RC,

Tôi hiểu câu hỏi của RC từ comment đầu. Để tôi rephrase lại câu trả lời như thế này:

giả sử tồn tại PCP verifier cho 3sat chạy trong poly-log time, thì có thể suy ra rằng một biến đổi địa phương như RC gợi ý không thể biến một công thức thỏa mãn được thành một công thức không thỏa mãn được. Tại vì, nếu S’ không thỏa mãn được thì verifier chỉ sai với sác xuất nhỏ hơn $1/100$ , bất kể chứng minh là gì.

Cái argument của RC có khả năng sẽ hợp lệ nếu như RC chứng minh được rằng tồn tại một thay đổi cục bộ của một công thức thỏa mãn được (cho trước, bất kỳ) để sản sinh ra một công thức không thỏa mãn được.

Lý do mà tôi nói là “có khả năng hợp lệ” là vì dù tồn tại một công thức S có tính chất trên, thì S’ có thể bị buộc phải ở một dạng đặc biệt nào đó mà verifier có thể kiểm tra “dạng đặc biệt” này dùng poly-log time. Ví dụ như, có khả năng là “biến đổi cục bộ” đó tồn tại nhưng không phải biến chỗ ngẫu nhiên nào trong $C_i$ cũng được mà phải biến ở một số vị trí đặc biệt thì mới được. Verifier chỉ cần nhìn vào các vị trí đặc biệt đó là xong. Hoặc là, “biến đổi cục bộ” đó chỉ tồn tại cho các S có dạng đặc biệt nào đó.

À, còn một điểm nữa có thể làm cho RC hiểu lầm. Bài toán mà chúng ta biết rằng có poly-log verifier là bài toán gap-max-3sat (và các loại gap-csp tương tự). Trong bài toán này thì yes-instance thỏa hết được, còn no-instance chỉ thỏa được một tỉ lệ nào đó (99% chẳng hạn) các clauses. Vì thế một biến đổi cục bộ không thể biến một yes-instance thành no-instance được.

Reply
Ngô Quang Hưng

Posted 24/08/2009 at 11:51 am | Permalink

Tôi không biết ý tưởng của RC có chứng minh được sự không tồn tại poly-log verifier hay không?

Nhưng nó thú vị ở chỗ từ đó có thể đặt một bài toán đối ngẫu với PCPP:

Trong PCPP thì, với input (x,y), ta chỉ cần verifier nói NO nếu chứng minh y “xa” chứng minh mệnh đề x.

Trong bài toán đối ngẫu thì ta cần verifier nói NO nếu x “xa” cái mệnh đề mà y chứng minh.

Reply
RongChoi

Posted 24/08/2009 at 12:10 pm | Permalink

Hi anh Hưng,

Trước nay RC nghĩ là anh Hưng thiên về việc có poly-log time verifier cho các bài toán tổng quát hoặc chí ít là cho SAT chứ đâu phải cho các bài gap-csp nhỉ?
Trong post [April 11, 2009 at 3:46 pm] anh Hưng có nói ” 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.”

OK, liệu có thể chúng ta đi đến thống nhất là: với một số bài toán NP đặc biệt thì có poly-log time verifier, còn hầu hết thì có lẽ là không, và như vậy, đối với hầu hết các bài NP, không có exp. speedup khi chuyển từ classical verifier sang PCP verifier.

Hi Thịnh,

Thịnh nói “vấn đề “read-once” có cần thiết hay không như vậy là đã rơi vào ngõ cụt ” có lẽ không thật chính xác. Định nghĩa nguyên thuỷ của NL là thông qua máy không đơn định. Còn certificate-based definition của NL là một alternative definition, và để cái định nghĩa này có ý nghĩa thì nó phải tương đương với định nghĩa nguyên thuỷ. Muốn chứng minh 2 định nghĩa là tương đương thì nhất thiết phải có hạn chế “read-once” cho verifier trong certificate-based definition của NL.

RC ko nhận được email nào cả, cái địa chỉ ở trường hiện tại dùng được, có đợt có 1, 2 ngày bị hỏng, chắc mail của Thịnh rơi trúng vào đợt đó

RC

Reply
RongChoi

Posted 24/08/2009 at 12:23 pm | Permalink

RC post trước khi đọc post cuối [August 24, 2009 at 11:51 am] của anh Hưng. Cách mô tả qua “bài toán đối ngẫu với PCPP” rất hay.

Ngoài ra, một bài toán nhỏ khác là: cho một công thức thoả được S, tìm S’ không thoả được sao cho số clauses trùng nhau trong S và S’ là lớn nhất.

Bài toán này không biết đã được xử lý chưa nhỉ? RC đoán là NP-hard.

Reply
Ngô Quang Hưng

Posted 24/08/2009 at 12:37 pm | Permalink

Hi RC,

Tôi nhắc đến gap-max-3sat vì muốn nói rằng argument của RC chắc chắn không áp dụng được trong trường hợp các bài gap-csp như gap-3sat.

Còn trong trường hợp của 3sat (hay bài toán NP tùy ý) thì, như đã nói, argument nọ cũng chưa áp dụng được vì cần phải chứng minh rằng local modification có thể biến một satistiable formula bất kỳ thành một unsatisfiable formula. Phát biểu này dường như rất mạnh và tôi chưa có cơ sở gì để tin là nó đúng.

Chúng ta có thể đi đến thống nhất là: RC đã làm cho tôi bớt tin là có poly-log verifier cho NP hơn.

Reply
Ngô Quang Hưng

Posted 24/08/2009 at 12:52 pm | Permalink

À, gần đây có một (tập) các bài toán khá thú vị phần nào liên quan đến câu hỏi của RC, xuất hiện trong bài báo này:

T. Ito, E. D. Demaine, N. J. A. Harvey, C. H. Papadimitriou, M. Sideri, R. Uehara and Y. Uno, On the complexity of reconfiguration problems, Proc. of ISAAC 2008, LNCS 5369 (2008) 28–39.

abstract: Reconfiguration problems arise when we wish to find a stepby-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. We demonstrate that a host of reconfiguration problems derived from NP-complete problems are PSPACE-complete, while some are also NP-hard to approximate. In contrast, several reconfiguration versions of problems in P are solvable in polynomial time.

Reply
Ngô Quang Hưng

Posted 24/08/2009 at 12:59 pm | Permalink

Ngoài ra, một bài toán nhỏ khác là: cho một công thức thoả được S, tìm S’ không thoả được sao cho số clauses trùng nhau trong S và S’ là lớn nhất.

RC phải đổi cái distance function, vì ta luôn có thể thêm vào $S$ 7 clauses làm cho $S'$ không thỏa được, và phần trùng nhau luôn là lớn nhất có thể (bằng với $S$ ). Lấy một clause bất kỳ của $S$ , ví cụ $(a \vee b \vee c)$ rồi thêm vào $(\bar a \vee b \vee c)$ , …, $(\bar a, \bar b, \bar c)$ .

Reply
RongChoi

Posted 24/08/2009 at 1:10 pm | Permalink

Ơ anh Hưng ơi, thế tức là coi như ta tìm được S với S’ khác nhau 7 clauses (ta có thể cho 7 clauses hằng đúng vào S) và S thỏa được, còn S’ không thỏa được nhé.
Nếu ta trộn một cách ngẫu nhiên 7 clauses hằng đúng vào S, và 7 clauses “mâu thuẫn nhau” vào S’ thì rõ ràng poly-log verifier sẽ chấp nhận một chứng minh WPCP(S) cho tính hằng đúng của S’ (với xác suất tương đương xác suất chấp nhận WPCP(S) cho S, trừ sai số poly-log(k)/k ~0) bằng cách lập luận phía trên?
Như vậy là không thể có poly-log verifier cho 3sat nhỉ?

Reply
Ngô Quang Hưng

Posted 24/08/2009 at 2:36 pm | Permalink

Hi RongChoi,

Đúng rồi. Thậm chí không có sub-linear verifier cho 3sat luôn. Vậy tôi hoàn toàn phải rút lại niềm tin nọ

Reply
ThinhNguyen

Posted 24/08/2009 at 7:34 pm | Permalink

@RongChoi:
Haha, cả RC và TN đều có nhầm lẫn nhỏ: bỏ “read-once” khỏi certificate-based def của NL có cho ta NP hay không nào ai đã biết. Nhưng đúng như RC nói “read-once” vẫn nằm đó vì construction của ta trong chứng minh sự tương đương của 2 definitions. Cái này có nhiều slide của các course, tha hồ xem.

Một cách ngắn gọn, nếu bỏ “read-once” thì chỉ với một counter (lưu trữ hết log-space) Verifier của ta có thể “dò dẫm” cái “certificate” nọ “poly many” lần. Trong khi đó, NL-machine nguyên thủy nào có đủ “ký ức” để “hồi tưởng” các “non-deterministic choices” mà nó đã “made”.

Vấn đề FL ?= FP hay L ?= P đều open cả.

Có cả một số monographs dạy ta cách xoay sở trong low-space. Một result hay hay là DSPACE( o( log log(n) ) ) = DSPACE(1). Nhưng DSPACE(log log (n)) strictly contains DSPACE(1). Và DSPACE(1) = REGULAR.

@anh Hưng
Về vấn đề “Chung qui chỉ tại Cantor”, em thấy còn xa xôi quá. Việc gần hơn là “P vs. NP” thậm chí còn bị chỉ trích từ thực tiễn rất nhiều lần như sau (đa phần là từ dân physics):

- Random sources: rất may cái này đang được conjecture là P=BPP nên có vẻ yên tâm. Poly-time quả là mạnh.

- Quantum: Tình hình của FACTORIZATION không giống như GRAPH-ISO. Thuật toán O(n^3) của Shor vẫn có thể chỉ nhanh hơn poly lần so với thuật toán O(n^10000000) của classical computing. Cơ bản là poly algo cho factorization không dẫn đến việc sập về level 2 của PH như thằng graph-iso. Không rõ có kết quả lý thuyết nào ủng hộ cho việc kô có poly algo cho factorization chưa nhỉ?

- Vẫn quantum: Ngay cả khi quantum computer kô thể hiện thực hóa được thì nó vẫn được dùng để cho ra chứng minh ngắn gọn cho một số kết quả cũ và mới. PostBQP=PP của Aaronson chắng hạn, dẫn đến chứng minh đơn giản cho việc PP đóng với intersection, trong khi Raz et.al chứng minh dài. Gần đây nữa là QIP=PSPACE.

- Vậy là rất khó đoán trước, quantum computing sẽ ảnh hưởng đến classical thế nào.

Reply
RongChoi

Posted 25/08/2009 at 4:51 am | Permalink

Hi anh Hưng,
Có thể có bài toán sau không tầm thường: cho một công thức thoả được S, tìm S’ không thoả được sao cho số clauses trùng nhau trong S và S’ là lớn nhất và tập gồm một nửa số clauses bất kỳ trong S’ thì vẫn thoả được (một nửa có thể thay bằng một tỉ lệ nào đó, log, x%,…, hoặc tối ưu lực lượng tập này).

Hi Thịnh,
RC không nghĩ là nhầm, bỏ “read-once” khỏi certificate-based def của NL sẽ cho ta NP. Chứng minh một cách ngắn gọn:
- Đầu tiên, verifier trong certificate-based def của NL khi cho quyền đọc thoải mái vẫn có sức mạnh kém verifier trong certificate-based def của NP vì số cấu hình có thể của verifier trong certificate-based def của NL chỉ là poly. Do vậy certificate-based def của NL không có điều kiện “read-once” cho ta một lớp không hơn NP.
- Ngược lại, phép qui dẫn của Cook-Levin từ mọi bài NP về SAT có thể thực hiện với log-space. Và cuối cùng, SAT có thể kiểm tra bằng verifier trong certificate-based def của NL khi bỏ điều kiện “read-once”. QED

Vấn đề NP = NL hay không tương đương điều kiện “read-once” có thực sự đem thêm sức mạnh hay không.
RC

Reply
Ngô Quang Hưng

Posted 25/08/2009 at 11:41 am | Permalink

Hi RC, định nghĩa bài toán hơi bị ép buộc. Cần motivation tốt hơn, nếu là động cơ từ một bài toán thực tế thì tốt nhất.

Reply
RongChoi

Posted 25/08/2009 at 1:48 pm | Permalink

Hi anh Hưng,
Ý nghĩa của bài toán nôm na là: tối thiểu hoá thông tin đưa vào mà ẩn chứa nhiều thông tin đặc trưng về công thức đang xét (S).
Thật vậy, nếu thông tin đưa vào độc lập với hầu hết các clauses của S, bản thân nó và thiểu số các clauses còn lại phải mâu thuẫn nhau (trong ví dụ đem vào 7 clauses mâu thuẫn với 1 clause như trên, tầm ảnh hưởng chỉ là 1/ số clauses). Do đó, nếu tìm được lời giải cho bài toán thì phần biến đổi (S-> S’) mã một dạng thông tin khá toàn cục về S.
RC

Reply
Ngô Quang Hưng

Posted 25/08/2009 at 5:55 pm | Permalink

Hi RC,

Tôi vẫn thấy cách đặt vấn đề chưa tự nhiên, vì thế bài toán có cảm giác bị ép về mặt định nghĩa. Ví dụ như tại sao lại chọn một distance function dùng tổng số clauses chung. Tôi nghĩ một cái gì đó liên quan đến Hamming distance thì có vẻ tự nhiên hơn. Ví dụ như ép S’ và S có cùng số clauses, xếp theo một thứ tự nhất định, rồi xem các “bits” trong các clauses khác nhau bao xa, dùng Hamming distance.

Quan trọng hơn, cần phải có một ứng dụng cụ thể để cho thấy cái định nghĩa của mình không bị artificial. Tôi nghĩ có thể S đại diện cho một “chìa khóa” mà Alice có, dùng để mở một cổng nào đó mà “ổ khóa” là một probabilistic verifier (PV). PV sẽ không kiểm tra hết chìa mà chỉ kiểm tra (probabilistically) một phần của chìa. Ngoài ra còn một ổ khóa xịn, giữ bí mật quốc gia, thì verifier là deterministic.

Bây giờ, Alice muốn cho Bob mượn chìa khóa, nhưng lại không muốn cho Bob biết toàn bộ cái khóa, thì Alice “modify” cái chìa để thành S’ không satisfiable nữa. Bob có thể dùng S’ để mở các ổ khóa mà mức độ bảo mật thường thường thôi, nhưng không thể dùng để mở một ổ khóa xịn.

Nói chung vẫn còn hoa tay múa chân nhiều, và ứng dụng trên tôi vẫn thấy bị ép buộc, artificial.

Reply
RongChoi

Posted 26/08/2009 at 2:06 am | Permalink

Hi anh Hưng,

Bài toán RC phát biểu đúng là còn thô, chúng ta hoàn toàn có thể biến đổi nó cho thú vị hơn.

Thực ra số clauses chung và Hamming distance RC thấy cũng như nhau. Khi chuẩn hóa cho S, S’ cùng số clauses và coi mỗi clauses là một đơn vị thì số clauses chung = 1 – min(Hamming distance) tính trên mọi cách sắp xếp. Nhưng đối với một công thức thì thứ tự các clauses không mang ý nghĩa đến tính thoả được nên RC thích dùng độ đo là giao của hai tập clauses.

Đúng là cần có ứng dụng thì bài toán mới hay và anh Hưng có lẽ đã cảm được là RC có nghĩ đến ứng dụng mật mã Nhưng vì ứng dụng RC nghĩ còn mơ hồ và chưa rõ nét nên chưa muốn trình bày.

Ứng dụng anh Hưng nói có một số điểm chưa hợp lý, Alice có thể dùng cách S+7 phía trên để tạo ra S’ và sau đó Bob có thể dùng S’+7 để tạo ra khoá khác đưa cho Eve. Ngoài ra, nếu S’ chứa nhiều thông tin về S như yêu cầu của bài toán (nếu không thì Alice có thể tạo S’ độc lập, và Bob cũng có thể bịa khoá độc lập) thì việc đưa S’ làm lộ quá nhiều thông tin.

Ứng dụng mơ hồ RC nghĩ là: Giả sử bài toán trên là khó, nhưng lại có cách xây dựng S một cách khá tự nhiên nhưng đặc biệt mà chỉ Alice biết để sao cho Alice có thể giải được bài toán. Khi đó S sẽ là công khai, vì bài toán là khó nên không tên địch nào tìm được S’ thoả mãn các điều kiện.

Khi đăng ký vào một Mafia club thì mỗi thành viên cần đăng ký S công khaithay cho tên tuổi, danh tính.
Để qua cổng vào cuộc họp kín, tất nhiên, nếu đưa S’ thì có thể qua, nhưng như vậy sẽ lộ S’.

- Thành viên của club chỉ cần chứng minh là tôi giải được bài toán, tức là biết S’, nhưng lại không muốn lộ S’ cho kẻ giữ cửa-thế giới mafia chả tên nào tin nhau. Muốn vậy thành viên sẽ commit các clauses của S’ (tức cho chúng vào phong bì bịt kín, theo phương pháp mật mã chứ không phải phong bì thật).
- Tên kiểm tra cửa chọn ngẫu nhiên vài phong bì và bắt thành viên mở, các clauses có nhiều khả năng thuộc S (S’ gần S) và thành viên qua bước 1 với xác suất lớn (với xác suất nhỏ, tên gác cổng bốc trúng phong bì chứa clause trong S’/S thì thành viên đi về). Nếu dừng ở đây thì lấy béng S’=S.
- Giờ thành viên phải chứng minh S thoả được còn S’ là không thoả được. Tính thoả được của S thuộc NP nên có thể chứng minh bằng PCP. Nhưng tính không thoả được của S’ là một bài toán có lẽ không thuộc NP (vì nếu thuộc NP thì co-NP = NP) nên PCP chưa giúp ích được gì. May quá, nó vẫn thuộc PSPACE và do vậy mà thành viên có thể chứng minh bằng zero-knowledge, tức chứng minh mà không để lộ tí thông tin nào về S’.
Thành viên qua cửa mà kẻ kiểm soát nói chung không biết được gì về thông tin S’/S.

RC

Reply
RongChoi

Posted 26/08/2009 at 2:23 am | Permalink

Trong ứng dụng trên, có thể thay đổi để khi đăng ký thành viên MafiaClub, cần cung cấp chứng minh PCP của S – chỉ những kẻ biết về PCP mới được đăng ký hội viên
Như vậy bước cuối cùng chỉ cần chứng minh tính không thoả được của S’ bằng zero-knowledge – chỉ những kẻ có khả năng giải quyết vấn đề (thực sụ có lời giải S’) mới được tham gia secret meeting.
RC

Reply
Ngô Quang Hưng

Posted 26/08/2009 at 9:26 am | Permalink

Hello RC,

Hamming distance hơi khác tổng số clauses chung một chút. Ví dụ có thể 2 clauses C1 & C2 khác nhau nhưng hamming distance giữa chúng có thể từ 1 đến 3 (hoặc k nếu các clauses này là k-CNF). Do đó, Hamming distance có lẽ là “nhạy cảm” hơn với thay đổi các clauses. Nói cho cùng, cái distance function phải phụ thuộc vào ứng dụng cụ thể, và vì thế bây giờ chưa có cơ sở gì để bàn.

Về ứng dụng thì nếu “Ổ khoá” có một thuật toán nào đó có tính chất sau đây: “chỉ cho mở khóa nếu như một tập con lớn bất kỳ của các clauses của S’ là thỏa được”, thì cái mẹo S+7 sẽ không thông nữa.

Cái MafiaClub nghe thú vị, nhưng tôi có cảm giác RC giết gà bằng dao mổ trâu.

Reply
RongChoi

Posted 27/08/2009 at 4:41 am | Permalink

Hi anh Hưng,
Tạm bỏ qua bài toán “Mafia giết gà”, RC chợt có 1 câu hỏi, có thể lời giải rất hiển nhiên nhưng cứ ghi lại:
Với 1 bài toán thuộc NP, từ một winess (hay chứng minh) cho máy kiểm tra đơn định, ta có thể xây dựng được chứng minh PCP. Vậy liệu ngược lại, nếu ta có chứng minh PCP, không còn bị ràng buộc về số bít đọc – tức là có thể đọc toàn bộ cái chứng minh PCP – thì liệu ta có xây dựng lại được (tất nhiên trong thời đa thức) cái winess ban đầu hay không?
Nếu có thể xây dựng được hàm biền đổi từ witness sang chứng minh PCP là hàm một chiều thì kể cũng rất thú vị.
RC

Reply