Count\((q)\) versus the pigeon-hole principle

DOI10.1007/s001530050060zbMath0884.03055OpenAlexW2728095097MaRDI QIDQ1360313

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

pigeonhole principleBounded Arithmeticcounting principles

Mathematics Subject Classification ID

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

Related Items

\(\text{Count}(q)\) does not imply \(\text{Count}(p)\) ⋮ NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Uniformly generated submodules of permutation modules over fields of characteristic 0.