Count(q) versus the pigeon-hole principle

DOI10.1007/S001530050060MaRDI QIDQ1360313zbMATH OpenOpenAlexFDO

Authors Søren Riis

Publication date 1 April 1998

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s001530050060

zbMATH Keywords

Bounded Arithmeticcounting principlespigeonhole principle

Mathematics Subject Classification ID

Classical propositional logic (03B05) Model-theoretic forcing (03C25) Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

The paper contributes to the area which studies the status of elementary counting principles (like pigeon-hole principle) in Bounded Arithmetic. Such questions are in a nontrivial way connected to some questions (like the well-known P-NP problem) in complexity theory. The author continues his previous work on solving the so-called \(\text{Count}(q)\) versus \(\text{Count}(p)\) problem; the main onstruction is here simplified. A complete classification of the mentioned \(\text{Count}(q)\) versus \(\text{Count}(p)\) problem is obtained as a corollary of the main technical theorem (which shows the existence of a certain model satisfying the \(\text{Count}(p)\) principle). Another corollary shows that the pigeon-hole principle for injective maps does not follow from any of the \(\text{Count}(q)\) principles; this solves an open question.

Recommendations

• The counting version of a problem of Erdős
• The complexity of the pigeonhole principle
• Quasipolynomial size proofs of the propositional pigeonhole principle
• Exponential lower bounds for the pigeonhole principle
• On the weak pigeonhole principle
• scientific article; zbMATH DE number 176196
• Pigeonholes and repunits
• On the power of enumerative counting
• Pigeonhole and Choice Principles

Cited in

(9)

• \(\text{Count}(q)\) does not imply \(\text{Count}(p)\)
• The ordering principle in a fragment of approximate counting
• Approximate counting by hashing in bounded arithmetic
• scientific article; zbMATH DE number 3912375 (Why is no real title available?)
• scientific article; zbMATH DE number 176196 (Why is no real title available?)
• scientific article; zbMATH DE number 2087215 (Why is no real title available?)
• NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN
• Approximate counting in bounded arithmetic
• Uniformly generated submodules of permutation modules over fields of characteristic 0.

This page was built for publication: Count\((q)\) versus the pigeon-hole principle

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