Interactive proof systems and alternating time-space complexity

DOI10.1016/0304-3975(93)90210-KzbMath0777.68039MaRDI QIDQ685437

Lance J. Fortnow, Carstent 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)

Related Items

Fast approximate probabilistically checkable proofs ⋮ 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

Cites Work

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