Logspace verifiers, NC, and NP
From MaRDI portal
Publication:6487945
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) Networks and circuits as models of computation; circuit complexity (68Q06)
Recommendations
Cites work
- scientific article; zbMATH DE number 4205986 (Why is no real title available?)
- scientific article; zbMATH DE number 4213437 (Why is no real title available?)
- scientific article; zbMATH DE number 4050986 (Why is no real title available?)
- scientific article; zbMATH DE number 176526 (Why is no real title available?)
- Algebraic methods for interactive proof systems
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- IP = SPACE
- Interactive proof systems and alternating time-space complexity
- On uniform circuit complexity
- Probabilistic game automata
- The Knowledge Complexity of Interactive Proof Systems
Cited in
(7)- scientific article; zbMATH DE number 4014037 (Why is no real title available?)
- Logspace Reducibility: Models and Equivalences
- Verifying proofs in constant depth
- Interactive proof systems and alternating time-space complexity
- Verifying proofs in constant depth
- Updateable Inner Product Argument with Logarithmic Verifier and Applications
- #NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes
This page was built for publication: Logspace verifiers, NC, and NP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6487945)
