Interactive proof systems and alternating time-space complexity (Q685437): Difference between revisions

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 \textit{L. Fortnow} and \textit{M. Sipser} [Interactive proof systems with a log space verifier, manuscript (1988)]; later version appeared in \textit{L. Fortnow} [Complexity-theoretic aspects of interactive proof systems, Ph. D. Thesis, Laboratory for Computer Science, Massachusetts Institute of Technology (1989)]. \(*\) All languages in \(P\) have interactive proofs with a polynomial-time public-coin verifier using \(O(\log^ 2n)\) 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.