Summary: We introduce a technique of arithmetization of the process of computation in order to obtain novel characterization of certain complexity classes via multivariate polynomials. A variety of concepts and tools of elementary algebras, such as the degree of polynomials and interpolation, becomes thereby available for the study of complexity classes.
The theory to be described provides a unified framework from which powerful recent results follow naturally.
The central result is a characterization of \(\#P\) in terms of arithmetic straight line programs. The consequences include a simplified proof of Toda’s theorem [S. Toda, On the computational power of \(PP\) and \(\oplus P\), in Proc. 30th Ann. IEEE Symp. Foundations of Comp. Sci., 514- 519 (1989)] that \(PH\subseteq P^{\#P}\); and an infinite class of natural and potential inequivalent functions, checkable in the sense of M. Blum [Designing programs that check their work, submitted to Comm. of Assoc. Comput. Mach.], M. Blum and S.Kannan [Designing programs that check their work, in Proc. 21st Ann. ACM Symp. Theory of Computing, 86-97 (1989)], and M. Blum, M. Luby and R. Rubinfeld [Self-testing and self-correcting programs, with applications to numerical programs, in Proc. 22nd Ann. ACM Symp. Theory of Computing, 73-83 (1990)]. Similar characterizations of PSPACE are also given.
The arithmetization technique has been introduced independently by A. Sharmir [IP=PSPACE, in Proc. 31st Ann. IEEE Symp. Foundations of Comp. Sci., 11-15 (1990)]. While this simultaneous discovery was driven by applications to interactive proofs, the present paper demonstrates the applicability of this technique to classical complexity classes.