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)

zbMATH Keywords

nondeterministic computationalternating time-space complexitylog-space polynomial-time public-coin verifierpolynomial-time public-coin verifierpublic- coin interactive proof systempublic-coin polynomial- space exponential-time verifiers

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 3571498 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• 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
• 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

(10)

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

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)