scientific article; zbMATH DE number 3912375
[For the entire collection see Zbl 0556.00007.] The paper is devoted to the counting problem in bounded arithmetic, namely to the following three still open problems: (1) Let A be a \(\Delta_ 0\) subset of N, then does the set \(\{<n,m>:\) \(m=| A\cap n| \}\) have a \(\Delta_ 0\) definition? (2) Let A be a \(\Delta_ 0\) subset of N, then for \(k\in N\) does \(\{<n,i>:\) \(i<k\) \& \(| A\cap n| =i mod k\}\) have a \(\Delta_ 0\) definition? (3) Does \(I\Delta_ 0\) \((=\) a fragment of Peano arithmetic with \(\Delta_ 0\) induction only) prove \(\Delta_ 0\) pigeon hole principle? The paper is a survey of results obtained in connection with these problems and contains a number of new results of the authors.
- 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)