Verifying proofs in constant depth

DOI10.1145/2462896.2462898MaRDI QIDQ2947574zbMATH OpenOpenAlexDBLPWikidataFDO

Authors

Publication date 24 September 2015

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL http://eprints.whiterose.ac.uk/79314/8/JournalRevision.pdf

zbMATH Keywords

proof complexitycircuit complexityproof circuitssmall depth proofs

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Recommendations

• Verifying proofs in constant depth
• DLOGTIME proof systems
• Logspace verifiers, NC, and NP

Cited in

(4)

• Verifying proofs in constant depth
• DLOGTIME proof systems
• Deep Proof Search in MELL
• A circuit complexity approach to transductions

This page was built for publication: Verifying proofs in constant depth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947574)