The main contribution of this paper is to state, in a general setting, the relationship between alternating time-space complexity classes ATISP(t,s) and public-coin interactive proof systems where the verifier has polynomially related time and space complexity IPTISP(t,s). The setting is general enough to cover special cases from NC (NC has interactive proofs with a logarithmic space, polynomial time verifier) to  EXPSPACE  (EXPSPACE has interactive proofs with exponential time and space verifiers), including the well-known IP = PSPACE result.

By way of establishing this relationship, the authors show efficient simulations of k-tape alternating Turing machines (ATMs) on 1-tape ATMs. This, combined with the main result, gives a tight hierarchy of IPTISP classes, as well as of IPTIME and IPSPACE classes. In particular, it establishes that linear time public coin interactive proof systems are strictly weaker than PSPACE, which is an interesting lower bound.

A nice feature of the paper is that, although it is quite technical, it is largely self-contained. The section on arithmetization of alternating computations is well written; the details may seem tedious but are easily understandable. Relevant references are cited at the appropriate places. The paper will be of general interest to complexity theorists.