scientific article; zbMATH DE number 1114025

MaRDI QIDQ4375795zbMATHFDO

Authors Alexis Maciel, Toniann Pitassi

Publication date 8 July 1998

zbMATH Keywords

lower boundsbounded-depth Frege proofscounting connectivesmodular connectivespropositional theorem provingquasipolynomial-size proofsthreshold connective

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Mechanization of proofs and logical operations (03B35) Complexity of proofs (03F20)

Recommendations

• scientific article; zbMATH DE number 1559592
• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
• Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
• Lifting lower bounds for tree-like proofs

Cited in

(7)

• Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
• Hard examples for the bounded depth Frege proof system
• Uniform proofs of ACC representations
• A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
• scientific article; zbMATH DE number 1559592 (Why is no real title available?)
• Approximation and Small-Depth Frege Proofs
• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting

This page was built for publication:

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