Hasnain says:

“The theorem gave a new understanding of NP and explained some of its intriguing properties. Computer scientists had found that for some NP problems, answers seemed not only hard to compute, but hard to approximate as well. The PCP theorem helped explain why. It said that if a solution to an NP problem was found, it could always be reformatted in a way where most checks from a verifier (say 90 percent) would pass (but not all of them, because the proof is still just probabilistic). From the vantage point of the verifier, it would therefore look like the problem was solved approximately, to 90 percent accuracy. But because NP problems are hard to solve, it is often difficult to find a PCP for them, and therefore it’s equally hard to find a solution that is approximately correct beyond a certain point (such as 90 percent).”

Posted on 2022-05-24T15:25:35+0000