Talk:PCP theorem

I feel that the proof of Lemma 1 is unnecessarily detailed. Also, the proof sketch of Lemma 2 skips the main point completely (!) in favor of elaborating the trivial equivalence between the PCP theorem and reductions to Max 3SAT in an unclear way. Dinur's proof should be cited and some sort of intuition given. It seems misleading to give lots of details on trivial pieces of the proof without saying anything about the interesting part of the proof. 131.215.48.236 (talk) 01:24, 9 July 2008 (UTC)Reply

Why Irit Dinur's is worth mentioning? Where are the third-party references which demonstrate its notability? - Altenmann >t 21:55, 21 July 2009 (UTC)Reply

See, for example, this survey Bravely, Moderately: A Common Theme in Four Recent Results, and also this one: On Dinur's Proof of the PCP Theorem. Also, beside the fact that the paper appeared in a really prestigious journal (J. ACM), it received the STOC/FOCS best paper award in 2006. Probably it would be valuable to explain in a few words why the new proof is worth mentioning (one reason is that it is by far simpler than the original one). Hermel (talk) 22:58, 21 July 2009 (UTC)Reply

What is know about the mentioned universal constant K? Have we named it? 195.77.88.65 (talk) 13:23, 23 March 2014 (UTC)Reply

I don't get how the promise problem presented relates to the problem of approximating the "maximum fraction of satisfiable constraints". I think for the discussion to make sense, the problems should be equivalent, or at least you should be able to reduce the promise problem to the approximation problem. I don't see how an approximate value for the maximum can help you solve the promise problem. Suppose a = 0.9 and suppose the for a particular \Phi the approximate value for the maximum is m = 0.9 +/- 0.2 . Then you won't be able to tell whether \Phi is in L_{yes} (m=1) or whether \Phi is in L_{no} (any m < 0.9). Maybe it should explain better what criterion for approximation is this using? 92.25.22.177 (talk) 19:22, 5 April 2015 (UTC)Reply

As far as I can tell, Feige, Goldwasser, Lund, Safra, and Szegedy did not publish any papers together in 1991. However, "Feige, Goldwasser, Lund, Safra, and Szegedy (1991)" is referenced in the article (with no references link I might add). U Feige, S Goldwasser, L Lovász, S Safra, and M Szegedy published "Approximating clique is almost NP-complete" in the same year; if Lund was credited in place of Lovász, this citation would make sense. Previously, the 1998 paper "Probabilistic checking of proofs: A new characterization of NP" by Arora and Safra was cited, while giving the year as 1992. I believe this to have been a miscitation, and have cited their 1992 paper, "Approximating clique is NP-complete" in its place. With this in mind, it certainly seems as though the 1991 paper by Feige, S Goldwasser, L Lovász, S Safra, and M Szegedy was the intended citation. --Cyrus Cousins (talk) 20:50, 30 April 2016 (UTC)Reply