Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- 1 September 1996
- journal article
- Published by Springer Science and Business Media LLC in computational complexity
- Vol. 6 (3), 256-298
- https://doi.org/10.1007/bf01294258
Abstract
No abstract availableKeywords
This publication has 32 references indexed in Scilit:
- An exponential separation between the matching principle and the pigeonhole principlePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- More on the relative strength of counting principlesDIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1997
- Some remarks on lengths of propositional proofsArchive for Mathematical Logic, 1995
- Lower bounds for cutting planes proofs with small coefficientsPublished by Association for Computing Machinery (ACM) ,1995
- The relative complexity of NP search problemsPublished by Association for Computing Machinery (ACM) ,1995
- The independence of the modulo p counting principlesPublished by Association for Computing Machinery (ACM) ,1994
- Approximation and Small-Depth Frege ProofsSIAM Journal on Computing, 1992
- Parity and the Pigeonhole PrinciplePublished by Springer Science and Business Media LLC ,1990
- Many hard examples for resolutionJournal of the ACM, 1988
- The complexity of the pigeonhole principlePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988