We show, under the assumption that factoring is hard, that a model of PV exists in which the polynomial hierarchy does not collapse to the linear hierarchy; that a model of S21 exists in which NP is not in the second level of the linear hierarchy; and that a model of S21 exists in which the polynomial hierarchy collapses to the linear hierarchy. Our methods are model-theoretic. We use the assumption about factoring to get a model in which the weak (...) pigeonhole principle fails in a certain way, and then work with this failure to obtain our results. As a corollary of one of the proofs, we also show that in S21 the failure of WPHP (for Σb1 definable relations) implies that the strict version of PH does not collapse to a finite level. (shrink)

Pudlák shows that bounded arithmetic proves an upper bound on the Ramsey number Rr . We will strengthen this result by improving the bound. We also investigate lower bounds, obtaining a non-constructive lower bound for the special case of 2 colors , by formalizing a use of the probabilistic method. A constructive lower bound is worked out for the case when the monochromatic set size is fixed to 3 . The constructive lower bound is used to prove two “reversals”. To (...) explain this idea we note that the Ramsey upper bound proof for k=3 uses the weak pigeonhole principle in a significant way. The Ramsey upper bound proof for the case in which the upper bound is not explicitly mentioned, uses the totality of the exponentiation function in a significant way. It turns out that the Ramsey upper bounds actually imply the respective principles used to prove them, indicating that these principles were in some sense necessary. (shrink)

Journal of Mathematical Logic, Volume 22, Issue 03, December 2022. We study a new class of NP search problems, those which can be proved total using standard combinatorial reasoning based on approximate counting. Our model for this kind of reasoning is the bounded arithmetic theory [math] of [E. Jeřábek, Approximate counting by hashing in bounded arithmetic, J. Symb. Log. 74(3) (2009) 829–860]. In particular, the Ramsey and weak pigeonhole search problems lie in the new 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 [math], this shows that [math] does not prove every [math] sentence which is provable in bounded arithmetic. This answers the question posed in [S. Buss, L. A. Kołodziejczyk and N. Thapen, Fragments of approximate counting, J. Symb. Log. 79(2) (2014) 496–525] and represents some progress in the program 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 [P. Pudlák and N. Thapen, Random resolution refutations, Comput. Complexity, 28(2) (2019) 185–239], 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 [math] oracle machine. The introduction to the paper is intended to make the statements and context of the results accessible to someone unfamiliar with NP search problems or with bounded arithmetic. (shrink)

We study the extension 123) of the theory S21 by instances of the dual weak pigeonhole principle for p-time functions, dWPHPx2x. We propose a natural framework for formalization of randomized algorithms in bounded arithmetic, and use it to provide a strengthening of Wilkie's witnessing theorem for S21+dWPHP. We construct a propositional proof system WF , which captures the Π1b-consequences of S21+dWPHP. We also show that WF p-simulates the Unstructured Extended Nullstellensatz proof system of Buss et al. 256). We prove that (...) dWPHP is equivalent to a statement asserting the existence of a family of Boolean functions with exponential circuit complexity. Building on this result, we formalize the Nisan–Wigderson construction in a conservative extension of S21+dWPHP. (shrink)

We study the long-standing open problem of giving$\forall {\rm{\Sigma }}_1^b$separations for fragments of bounded arithmetic in the relativized setting. Rather than considering the usual fragments defined by the amount of induction they allow, we study Jeřábek’s theories for approximate counting and their subtheories. We show that the$\forall {\rm{\Sigma }}_1^b$Herbrandized ordering principle is unprovable in a fragment of bounded arithmetic that includes the injective weak pigeonhole principle for polynomial time functions, and also in a fragment that includes the surjective weak pigeonhole (...) principle for FPNPfunctions. We further give new propositional translations, in terms of random resolution refutations, for the consequences of$T_2^1$augmented with the surjective weak pigeonhole principle for polynomial time functions. (shrink)

We show that for each n ≥ 1, if T2n does not prove the weak pigeonhole principle for Σbn functions, then the collection scheme B Σ1 is not finitely axiomatizable over T2n. The same result holds with Sn2 in place of T 2n.