Interactive proof systems and alternating time—space complexity

We show a rough equivalence between alternating time-space complexity and a public-coin interactive proof system with the verifier having a polynomial-related time-space complexity. Special cases include the following: • All of NC has interactive proofs, with a log-space polynomial-time public-coin verifier vastly improving the best previous lower bound of LOGCFL for this model (Fortnow and Sipser, 1988). • All languages in P have interactive proofs with a polynomial-time public-coin verifier using o(log2 n) space. • All exponential-time languages have interactive proof systems with public-coin polynomial-space exponential-time verifiers. To achieve better bounds, we show how to reduce a k-tape alternating Turing machine to a 1-tape alternating Turing machine with only a constant factor increase in time and space.

Authors

• Lance Fortnow
• Carsten Lund

Keywords

No keywords are indexed for this paper.