Probabilistically checkable proofs
Madhu Sudan · IAS/Park City mathematics series · 2004
Can a proof be checked without reading it?That certainly seems impossible, no matter how much reviewers of mathematical papers may wish for this.But theoretical computer science has shown that we can get very close to this objective!Namely random consistency checks could reveal errors in proofs, provided one is careful in choosing the format in which proofs should be written.In this article we explain this notion, constructions of such probabilistically checkable proofs, and why this is important to all of combinatorial optimization.