The independence of the modulo p counting principles

DOI10.1145/195058.195207zbMath1345.03103OpenAlexW2074052574MaRDI QIDQ2817631

Miklós Ajtai

Publication date: 1 September 2016

Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/195058.195207

Mathematics Subject Classification ID

Representations of finite symmetric groups (20C30) Complexity of proofs (03F20)

Related Items (8)

Unnamed Item ⋮ Proof complexity in algebraic systems and bounded depth Frege systems with modular counting ⋮ \(\text{Count}(q)\) does not imply \(\text{Count}(p)\) ⋮ A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝 Frege systems] ⋮ Towards NP-P via proof complexity and search ⋮ Forcing in Finite Structures ⋮ Uniformly generated submodules of permutation modules over fields of characteristic 0. ⋮ Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies

This page was built for publication: The independence of the modulo p counting principles