Interactive proof systems and alternating time-space complexity

DOI10.1016/0304-3975(93)90210-KzbMATH Open0777.68039MaRDI QIDQ685437FDOQ685437

Authors: Lance Fortnow, C. Lund 

Publication date: 15 December 1993

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• On the complexity of interactive proofs with bounded communication
• 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)