Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario Proof verification and the hardness of approximation problems. (English) Zbl 1065.68570 J. ACM 45, No. 3, 501-555 (1998). Cited in 9 ReviewsCited in 197 Documents MSC: 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 03B35 Mechanization of proofs and logical operations 03D15 Complexity of computation (including implicit computational complexity) 68Q25 Analysis of algorithms and problem complexity PDF BibTeX XML Cite \textit{S. Arora} et al., J. ACM 45, No. 3, 501--555 (1998; Zbl 1065.68570) Full Text: DOI