scientific article; zbMATH DE number 1114025

zbMATH Open0891.03027MaRDI QIDQ4375795FDOQ4375795

Alexis Maciel, Toniann Pitassi

Publication date: 8 July 1998

Title of this publication is not available (Why is that?)

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

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)

Cited In (7)

• A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
• Title not available (Why is that?)
• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
• Hard examples for the bounded depth Frege proof system
• Approximation and Small-Depth Frege Proofs
• Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
• Uniform proofs of ACC representations

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)