[Proof Complexity] preprint

[Leszek Kolodziejczyk]

Dear Colleagues,

Neil Thapen and I have a new preprint titled "Approximate counting and NP
search problems", which can be found for instance at:

https://arxiv.org/abs/1812.10771

The abstract is below. Comments, suggestions, and corrections will be
greatly appreciated.

Best regards,
Leszek

-----------------------------

Abstract:

We study a new class of NP search problems, those which can be proved total
in the theory APC_2 of [Jeřábek 2009]. This is an axiomatic theory in
bounded arithmetic which can formalize standard combinatorial arguments
based on approximate counting. In particular, the Ramsey and weak
pigeonhole search problems lie in the class. We give a purely computational
characterization of this class and show that, relative to an oracle, it
does not contain the problem CPLS, a strengthening of PLS.


As CPLS is provably total in the theory T^2_2, this shows that APC_2 does
not prove every \forall \Sigma^b_1 sentence which is provable in bounded
arithmetic. This answers the question posed in

[Buss, Kołodziejczyk, Thapen 2014] and represents some progress in the
programme of separating the levels of the bounded arithmetic hierarchy by
low-complexity sentences.


Our main technical tool is an extension of the "fixing lemma" from [Pudlák,
Thapen 2017], a form of switching lemma, which we use to show that a random
partial oracle from a certain distribution will, with high probability,
determine an entire computation of a P^NP oracle machine. The paper is
intended to be accessible to someone unfamiliar with NP search problems or
with bounded arithmetic.