Interactive and probabilistic proof-checking

The notion of efficient proof-checking has always been central to complexit y theory, and it gave rise to the definition of the class NP. In the last 1 5 years there has been a number of exciting, unexpected and deep developmen ts in complexity theory that exploited the notion of randomized and interac tive proof-checking. Results developed along this line of research have div erse and powerful applications in complexity theory, cryptography, and the theory of approximation algorithms for combinatorial optimization problems. In this paper we survey the main lines of developments in interactive and probabilistic proof-checking, with an emphasis on open questions. (C) 2000 Elsevier Science B.V. All rights reserved. MSC. 68Q10; 68Q15; 68Q17; 03F20.