Interactive proof systems and alternating time-space complexity
From MaRDI portal
Publication:685437
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)
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
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