|
Interactive proof systems and alternating time-space complexity Fortnow L., Lund C. Theoretical Computer Science 113(1): 55-73, 1993. Type: Article
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 ...
|
Jul 1 1994 |