[Proof Complexity] New paper on Bounded Arithmetic and Pigeonhole Principle
Mykyta Narusevych
mykyta.narusevych at matfyz.cuni.cz
Tue Sep 6 06:59:38 CEST 2022
Dear colleagues,
I have a new paper regarding unprovability of the pigeonhole principle inside fragments of bounded arithmetic, see https://arxiv.org/abs/2208.14713.
In particular, we prove that the theory T_2^1(R) extended by instances of the weak pigeonhole principle for polynomial-time predicates with oracle access to R is not able to prove that R itself does not violate the usual pigeonhole principle. The proof in the paper avoids switching lemma and relies upon the forcing technique only.
We also achieve the following result: the theory T_2^1(R) extended by instances of the pigeonhole principle up to n^{1 - \epsilon} for polynomial-time predicates with oracle access to R is not able to prove a pigeonhole principle up to n stated for R. This can be seen as a step towards an open problem first stated by M. Ajtai.
With regards,
Narusevych Mykyta
More information about the Proof-Complexity
mailing list