2 ms·
Basically, given a proof P of a statement expressed in n bits, you can in polynomial time with respect to n create a new PCP proof Q which spreads out (somehow?
by aston 20y ago
Basically, given a proof P of a statement expressed in n bits, you can in polynomial time with respect to n create a new PCP proof Q which spreads out (somehow?) P, including the errors in P. Since the errors are spread out, with high probability, you'll catch an error choosing a very small number of bits of Q.
It's like MAGIC... Especially since they don't explain it at all in the article.
http://en.wikipedia.org/wiki/PCP_theorem http://en.wikipedia.org/wiki/PCP_theorem
- dfranke 20y agoHmm. According to that, the theorem applies to propositional logic. Propositional logic is a very weak system; I don't think it can state the Riemann hypothesis. Edit: I take that back: propositional logic definitely can't state the Riemann hypothesis. PropLog is complete, which means that by Goedel's incompleteness theorem it can't even model the natural numbers, much less the complexes.