Interactive proof systems and alternating time-space complexity

DOI10.1016/0304-3975(93)90210-KMaRDI QIDQ685437zbMATH OpenFDO

Authors Lance Fortnow, C. Lund

Publication date 15 December 1993

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(93)90210-K

zbMATH Keywords

alternating time-space complexitylog-space polynomial-time public-coin verifiernondeterministic computationpolynomial-time public-coin verifierpublic- coin interactive proof systempublic-coin polynomial- space exponential-time verifiers

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 176510
• On the complexity of interactive proofs with bounded communication
• Logspace verifiers, NC, and NP
• Interactive proof systems with public coin: lower space bounds and hierarchies of complexity classes
• scientific article; zbMATH DE number 512981

Cites work

• A Note Concerning Nondeterministic Tape Complexities
• Algebraic methods for interactive proof systems
• Alternation
• Are there interactive protocols for co-NP languages?
• Arithmetization: A new method in structural complexity theory
• Erratum: A Fast Monte-Carlo Test for Primality
• scientific article; zbMATH DE number 3571498 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• IP = PSPACE
• On alternation
• On the Tape Complexity of Deterministic Context-Free Languages
• On time-space classes and their relation to the theory of real addition
• On uniform circuit complexity
• The Knowledge Complexity of Interactive Proof Systems

Cited in

(11)

• Fast approximate probabilistically checkable proofs
• Spooky interaction and its discontents: compilers for succinct two-message argument systems
• On the complexity of interactive proofs with bounded communication
• Amplifying circuit lower bounds against polynomial time, with applications
• scientific article; zbMATH DE number 176510 (Why is no real title available?)
• Interactive proofs and the hardness of approximating cliques
• Shorter arithmetization of nondeterministic computations
• Interactive proof systems with public coin: lower space bounds and hierarchies of complexity classes
• Constant-Round Interactive Proof Systems for AC0[2] and NC1
• Logspace verifiers, NC, and NP
• \(\mathrm{P}\) has polynomial-time finite-state verifiers

This page was built for publication: Interactive proof systems and alternating time-space complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685437)