\(\text{Count}(q)\) does not imply \(\text{Count}(p)\)

DOI10.1016/S0168-0072(97)00029-8zbMath0891.03030MaRDI QIDQ1377601

Søren Riis

Publication date: 28 June 1998

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

computational complexitybounded arithmeticforcing in arithmetic

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity of proofs (03F20)

Related Items (3)

Proof complexity in algebraic systems and bounded depth Frege systems with modular counting ⋮ Uniformly generated submodules of permutation modules over fields of characteristic 0. ⋮ The Complexity of Propositional Proofs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Combinatorial principles in elementary number theory
• The complexity of the pigeonhole principle
• Representing Boolean functions as polynomials modulo composite numbers
• Count\((q)\) versus the pigeon-hole principle
• The independence of the modulo p counting principles
• Polynomial size proofs of the propositional pigeonhole principle
• The relative efficiency of propositional proof systems
• Provability of the pigeonhole principle and the existence of infinitely many primes
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs

This page was built for publication: \(\text{Count}(q)\) does not imply \(\text{Count}(p)\)