Interactive proof systems and alternating time-space complexity

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On uniform circuit complexity
• Alternation
• 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
• Erratum: A Fast Monte-Carlo Test for Primality

Cited In (9)

• Constant-Round Interactive Proof Systems for AC0[2] and NC1
• 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
• Amplifying circuit lower bounds against polynomial time, with applications
• Shorter arithmetization of nondeterministic computations
• Spooky Interaction and Its Discontents: Compilers for Succinct Two-Message Argument Systems
• Interactive proofs and the hardness of approximating cliques

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• 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 👍 👎

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)