scientific article; zbMATH DE number 1114015

zbMATH Open0891.03025MaRDI QIDQ4375784FDOQ4375784

Authors: Søren Riis, Paul Beame 

Publication date: 8 February 1998

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

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

zbMATH Keywords

exponential lower boundspigeonhole principlebounded-depth Frege proofsmodular counting principles

Mathematics Subject Classification ID

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

Cited In (7)

• Title not available (Why is that?)
• 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
• A new proof of the weak pigeonhole principle
• The independence of the modulo \(p\) counting principles
• 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)