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 210 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 Citations:Zbl 0903.68076; Zbl 0765.68036; Zbl 0882.68129 PDF BibTeX XML Cite \textit{S. Arora} et al., J. ACM 45, No. 3, 501--555 (1998; Zbl 1065.68570) Full Text: DOI OpenURL