Optimal proof systems and sparse sets

DOI10.1007/3-540-46541-3_34MaRDI QIDQ4501551zbMATH OpenFDO

Authors Harry Buhrman, Steve Fenner, Dieter Van Melkebeek, Lance Fortnow

Publication date 4 September 2000

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

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

zbMATH Keywords

complexity class separationproof complexity

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Optimal proof systems for propositional logic and complete sets
• Optimal proof systems imply complete sets for promise classes
• On Sparse Complete Sets

Cited in

(11)

• Optimal proof systems imply complete sets for promise classes
• Error-bounded probabilistic computations between MA and AM
• Optimal indecomposable witnesses without extremality or the spanning property
• Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes
• Towards NP-P via proof complexity and search
• On optimal algorithms and optimal proof systems
• scientific article; zbMATH DE number 1929970 (Why is no real title available?)
• OPTIMAL PROOFS OF DETERMINACY II
• NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN
• PROOF MINING IN L^p SPACES
• scientific article; zbMATH DE number 5201477 (Why is no real title available?)

This page was built for publication: Optimal proof systems and sparse sets

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