scientific article; zbMATH DE number 1114015

MaRDI QIDQ4375784zbMATH OpenFDO

Authors Søren Riis, Paul Beame

Publication date 8 February 1998

zbMATH Keywords

exponential lower boundspigeonhole principlebounded-depth Frege proofsmodular counting principles

Mathematics Subject Classification ID

Classical propositional logic (03B05) Complexity of proofs (03F20)

Recommendations

• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles
• Exponential lower bounds for the pigeonhole principle

Cited in

(7)

• scientific article; zbMATH DE number 7561747 (Why is no real title available?)
• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
• Typical forcings, NP search problems and an extension of a theorem of Riis
• The independence of the modulo \(p\) counting principles
• A new proof of the weak pigeonhole principle
• Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
• Adventures in monotone complexity and TFNP

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 Q4375784)