scientific article; zbMATH DE number 176196

MaRDI QIDQ4035300zbMATH OpenFDO

Authors Miklós Ajtai

Publication date 18 May 1993

zbMATH Keywords

formal arithmeticPigeonhole Principle

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30)

Recommendations

• The complexity of the pigeonhole principle
• Count\((q)\) versus the pigeon-hole principle
• A parity-based Frege proof for the symmetric pigeonhole principle
• The Pigeonhole Principle and Fragments of Arithmetic
• An exponential separation between the parity principle and the pigeonhole principle

Cited in

(13)

• Count\((q)\) versus the pigeon-hole principle
• \(\text{Count}(q)\) does not imply \(\text{Count}(p)\)
• Deterministic summation modulo \(\mathcal B_{n}\), the semigroup of binary relations on \(0,1, \dots, n-1\)
• Cutting planes, connectivity, and threshold logic
• An exponential separation between the parity principle and the pigeonhole principle
• Propositional proof systems based on maximum satisfiability
• A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
• scientific article; zbMATH DE number 21650 (Why is no real title available?)
• The pigeonhole principle, two centuries before Dirichlet
• Another arithmetic of the even and the odd
• DRAT and propagation redundancy proofs without new variables
• On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems
• Strength and limitations of Sherali-Adams and nullstellensatz proof systems

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