PCP theorem and its applications to research on non-approximatable problems
Daoyun Xu · Jisuanji kexue yu tansuo · 2008
The PCP theorem is one of important results in complexity for recent ten years. The paper introduces the evolution from Turing computation model to the Probabilistically Checkable Proofs(PCP), the basic theory of PCP and its principle and approach to non-approximatable problems.