The complexity of generating and checking proofs of membership

DOI10.1007/3-540-60922-9_7MaRDI QIDQ4593919zbMATH OpenOpenAlexFDO

Authors Harry Buhrman, Thomas Thierauf

Publication date 16 November 2017

Published in STACS 96 (Search for Journal in Brave)

Full work available at URL https://ir.cwi.nl/pub/1332

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1256635
• Probabilistic checking of proofs
• scientific article; zbMATH DE number 1072533
• scientific article; zbMATH DE number 1775405
• Mathematical Foundations of Computer Science 2003

Cited in

(6)

• Some structural properties of SAT
• Relativized worlds with an infinite hierarchy
• scientific article; zbMATH DE number 1335878 (Why is no real title available?)
• scientific article; zbMATH DE number 1875423 (Why is no real title available?)
• Resource-bounded Kolmogorov complexity revisited
• Parametric Verification of a Group Membership Algorithm

This page was built for publication: The complexity of generating and checking proofs of membership

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