Efficient probabilistically checkable proofs and applications to approximations. (English) Zbl 1310.68083

Bellare, M.; Goldwasser, S.; Lund, C.; Russell, A.

Proceedings of the 25th annual ACM symposium on theory of computing, STOC ’93. San Diego, CA, USA, May 16–18, 1993. New York, NY: Association for Computing Machinery (ACM) (ISBN 0-89791-591-7). 294-304 (1993); corrigendum in STOC ’94, 820 (1994).

For the entire collection see [Zbl 1285.68003].

MSC:

68Q15	Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q87	Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)