Interactive proof systems and alternating time-space complexity

DOI10.1007/BFB0020804MaRDI QIDQ4035675zbMATH OpenFDO

Authors Lance Fortnow, C. Lund

Publication date 18 May 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0020804

zbMATH Keywords

alternating time-space complexitypublic-coin interactive proof system

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

Recommendations

• Interactive proof systems and alternating time-space complexity
• scientific article; zbMATH DE number 512803
• Interactive proofs with space bounded provers
• The Knowledge Complexity of Interactive Proof Systems
• The knowledge complexity of interactive proof-systems
• Interactive proof systems with polynomially bounded strategies
• Time-optimal interactive proofs for circuit evaluation
• Relativization and interactive proof systems in parameterized complexity theory
• Interactive proofs with approximately commuting provers
• scientific article; zbMATH DE number 512981

Cited in

(7)

• On the complexity of interactive proofs with bounded communication
• Interactive proof systems with public coin: lower space bounds and hierarchies of complexity classes
• Constant-Round Interactive Proof Systems for AC0[2] and NC1
• Alternation in interaction
• Logspace verifiers, NC, and NP
• Constant-round arguments from one-way functions
• Interactive proof systems and alternating time-space complexity

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 Q4035675)