It has been described by Ingo Wegener as "the most important result in complexity theory since Cook's theorem"[1] and by Oded Goldreich as "a culmination of a sequence of impressive works […] rich in innovative ideas".
The other characterisation of the PCP theorem then guarantees the promise condition with α = 1/2: if the NP problem's answer is yes, then every constraint (which corresponds to a particular value for the random bits) has a satisfying assignment (an acceptable proof); otherwise, any proof should be rejected with probability at least 1/2, which means any assignment must satisfy fewer than 1/2 of the constraints (which means it will be accepted with probability lower than 1/2).
These results are sometimes also called PCP theorems because they can be viewed as probabilistically checkable proofs for NP with some additional structure.
The 2001 Gödel Prize was awarded to Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan, and Mario Szegedy for work on the PCP theorem and its connection to hardness of approximation.
In 2005 Irit Dinur discovered a significantly simpler proof of the PCP theorem, using expander graphs.
[6] In 2012, Thomas Vidick and Tsuyoshi Ito published a result[7] that showed a "strong limitation on the ability of entangled provers to collude in a multiplayer game".
This could be a step toward proving the quantum analogue of the PCP theorem, since when the result[7] was reported in the media,[8][9] professor Dorit Aharonov called it "the quantum analogue of an earlier paper on multiprover interactive proofs" that "basically led to the PCP theorem".
[9] In 2018, Thomas Vidick and Anand Natarajan proved[10] a games variant of quantum PCP theorem under randomized reduction.