scientific article; zbMATH DE number 3912375

MaRDI QIDQ3689182zbMATH OpenFDO

Authors Jeff Paris, A. J. Wilkie

Publication date 1985

zbMATH Keywords

pigeon hole principlesurvey

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30)

Recommendations

• Count\((q)\) versus the pigeon-hole principle
• Provability of the pigeonhole principle and the existence of infinitely many primes
• \(\text{Count}(q)\) does not imply \(\text{Count}(p)\)
• Approximate counting by hashing in bounded arithmetic
• Bounded Induction and Satisfaction Classes

Cited in

(46)

• Complexity-theoretic hierarchies induced by fragments of Gödel's \(T\)
• A generalized Grzegorczyk hierarchy and low complexity classes
• Combinatorial principles in elementary number theory
• Bounded arithmetic, proof complexity and two papers of Parikh
• The complexity of the pigeonhole principle
• \(\text{Count}(q)\) does not imply \(\text{Count}(p)\)
• Some consequences of cryptographical conjectures for \(S_2^1\) and EF
• Deterministic summation modulo \(\mathcal B_{n}\), the semigroup of binary relations on \(0,1, \dots, n-1\)
• A model-theoretic characterization of the weak pigeonhole principle
• Nonerasing, counting, and majority over the linear time hierarchy
• \(\Delta_ 0\)-complexity of the relation \(y= \prod_{i\leq n} F(i)\)
• Cutting planes, connectivity, and threshold logic
• Transfinite induction within Peano arithmetic
• An exponential separation between the parity principle and the pigeonhole principle
• The treewidth of proofs
• Two problems on interval counting
• The canonical pairs of bounded depth Frege systems
• Partially definable forcing and bounded arithmetic
• Induction rules in bounded arithmetic
• Circuit principles and weak pigeonhole variants
• Typical forcings, NP search problems and an extension of a theorem of Riis
• Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
• Build your own clarithmetic. I: Setup and completeness
• Counting Δ_0 sets
• Approximate counting by hashing in bounded arithmetic
• On the correspondence between arithmetic theories and propositional proof systems – a survey
• On bounded arithmetic augmented by the ability to count certain sets of primes
• A Characterisation of Definable NP Search Problems in Peano Arithmetic
• scientific article; zbMATH DE number 4033719 (Why is no real title available?)
• Towards NP-P via proof complexity and search
• scientific article; zbMATH DE number 727438 (Why is no real title available?)
• A note on SAT algorithms and proof complexity
• Approximate counting and NP search problems
• scientific article; zbMATH DE number 6028114 (Why is no real title available?)
• Approximate counting in bounded arithmetic
• A new proof of the weak pigeonhole principle
• Computation models and function algebras
• Some consequences of cryptographical conjectures for S 2 1 and EF
• On the computational complexity of cut-reduction
• Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
• Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 12--17, 2023
• First-order reasoning and efficient semi-algebraic proofs
• On the consistency of stronger lower bounds for \(\mathsf{NEXP}\)
• The strength of the dominance rule
• On the complexity of counting in the polynomial hierarchy
• Resolution proofs of generalized pigeonhole principles

This page was built for publication:

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