Multi-oracle interactive protocols with space bounded verifiers
Uriel Feige, Adi Shamir · 2003
It is proved that both in the multiprover model of M. Ben-or et al. (Proc. 20th Symp. Theory Comput., 1988, p.113-131) and in the the noisy oracle model of U. Feige et al. (Proc. CRYPTO 88) a finite-state verifier can accept any recursive language. The power of verifiers with simultaneous time bounds and space bounds is considered as well.>