Logspace verifiers, NC, and NP

DOI10.1007/BFB0015408zbMATH Open1512.68105MaRDI QIDQ6487945FDOQ6487945

Authors: Satyanarayana V. Lokam, Meena Mahajan, V. Vinay 

Publication date: 21 March 2023

Recommendations

• Interactive proof systems and alternating time-space complexity
• scientific article; zbMATH DE number 66620
• scientific article; zbMATH DE number 176510
• Verifying proofs in constant depth
• scientific article; zbMATH DE number 5485522

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) Networks and circuits as models of computation; circuit complexity (68Q06)

Cites Work

• On uniform circuit complexity
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• The Knowledge Complexity of Interactive Proof Systems
• Interactive proof systems and alternating time-space complexity
• Algebraic methods for interactive proof systems
• Title not available (Why is that?)
• IP = SPACE
• Probabilistic game automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (7)

• Title not available (Why is that?)
• Logspace Reducibility: Models and Equivalences
• Verifying proofs in constant depth
• Verifying proofs in constant depth
• Interactive proof systems and alternating time-space complexity
• 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)