We develop approximate counting of sets definable by Boolean circuits in bounded arithmetic using the dual weak pigeonhole principle (dWPHP(PV)), as a generalization of results from [15]. We discuss applications to formalization of randomized complexity classes (such as BPP, APP, MA, AM) in PV₁ + dWPHP(PV).

We prove that the sharply bounded arithmetic T02 in a language containing the function symbol ⌊x /2y⌋ is equivalent to PV1.

We give a new characterization of the strict $$\forall {\Sigma^b_j}$$ sentences provable using $${\Sigma^b_k}$$ induction, for 1 ≤ j ≤ k. As a small application we show that, in a certain sense, Buss’s witnessing theorem for strict $${\Sigma^b_k}$$ formulas already holds over the relatively weak theory PV. We exhibit a combinatorial principle with the property that a lower bound for it in constant-depth Frege would imply that the narrow CNFs with short depth j Frege refutations form a strict hierarchy with (...) j, and hence that the relativized bounded arithmetic hierarchy can be separated by a family of $$\forall {\Sigma^b_1}$$ sentences. (shrink)

We show how to formalize approximate counting via hash functions in subsystems of bounded arithmetic, using variants of the weak pigeonhole principle. We discuss several applications, including a proof of the tournament principle, and an improvement on the known relationship of the collapse of the bounded arithmetic hierarchy to the collapse of the polynomial-time hierarchy.

The purpose of this paper is to survey the correspondence between bounded arithmetic and propositional proof systems. In addition, it also contains some new results which have appeared as an extended abstract in the proceedings of the conference TAMC 2008 [11].Bounded arithmetic is closely related to propositional proof systems; this relation has found many fruitful applications. The aim of this paper is to explain and develop the general correspondence between propositional proof systems and arithmetic theories, as introduced by Krajíček and (...) Pudlák [46]. Instead of focusing on the relation between particular proof systems and theories, we favour a general axiomatic approach to this correspondence. In the course of the development we particularly highlight the role played by logical closure properties of propositional proof systems, thereby obtaining a characterization of extensions of EF in terms of a simple combination of these closure properties (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

We study variants of Buss’s theories of bounded arithmetic axiomatized by induction schemes disallowing the use of parameters, and closely related induction inference rules. We put particular emphasis on \ induction schemes, which were so far neglected in the literature. We present inclusions and conservation results between the systems and \ of a new form), results on numbers of instances of the axioms or rules, connections to reflection principles for quantified propositional calculi, and separations between the systems.

We define and study a new restricted consistency notion RCon ∗ for bounded arithmetic theories T 2 j . It is the strongest ∀ Π 1 b -statement over S 2 1 provable in T 2 j , similar to Con in Krajíček and Pudlák, 29) or RCon in Krajı́ček and Takeuti 107). The advantage of our notion over the others is that RCon ∗ can directly be used to construct models of T 2 j . We apply this by (...) proving preservation theorems for theories of bounded arithmetic of the following well-known kind: The ∀ Π 1 b -separation of bounded arithmetic theories S 2 i from T 2 j is equivalent to the existence of a model of S 2 i which does not have a Δ 0 b -elementary extension to a model of T 2 j . More specific, let M ⊨ Ω 1 nst denote that there is a nonstandard element c in M such that the function n ↦ 2 log c is total in M . Let BLΣ 1 b be the bounded collection schema for Σ 1 b -formulas. We obtain the following preservation results: the ∀ Π 1 b -separation of S 2 i from T 2 j is equivalent to the existence of 1. a model of S 2 i +Ω 1 nst which is 1 b -closed w.r.t. T 2 j , 2. a countable model of S 2 i + BLΣ 1 b without weak end extensions to models of T 2 j. (shrink)

We prove that: • if there is a model of I∆₀ + ¬ exp with cofinal Σ₁-definable elements and a Σ₁ truth definition for Σ₁ sentences, then I∆₀ + ¬ exp +¬BΣ₁ is consistent, • there is a model of I∆₀ Ω₁ + ¬ exp with cofinal Σ₁-definable elements, both a Σ₂ and a ∏₂ truth definition for Σ₁ sentences, and for each n > 2, a Σ n truth definition for Σ n sentences. The latter result is obtained by (...) constructing a model with a recursive truth-preserving translation of Σ₁ sentences into boolean combinations of $\exists \sum {\begin{array}{*{20}{c}} h \\ 0 \\ \end{array} } $ sentences. We also present an old but previously unpublished proof of the consistency of I∆₀ + ¬ exp + ¬BΣ₁ under the assumption that the size parameter in Lessan's ∆₀ universal formula is optimal. We then discuss a possible reason why proving the consistency of I∆₀ + ¬ exp + ¬BΣ₁ unconditionally has turned out to be so difficult. (shrink)

We prove that PTCN cannot be a model of U12. This implies that there exists a first order sentence of bounded arithmetic which is provable in U12 but does not hold in PTCN.

We prove the following results: (i) PV proves NP ⊆ P/poly iff PV proves coNP ⊆ NP/O(1). (ii) If PV proves NP ⊆ P/poly then PV proves that the Polynomial Hierarchy collapses to the Boolean Hierarchy. (iii) $S_{2}^{1}$ proves NP ⊆ P/poly iff $S_{2}^{1}$ proves coNP ⊆ NP/O(log n). (iv) If $S_{2}^{1}$ proves NP ⊆ P/poly then $S_{2}^{1}$ proves that the Polynomial Hierarchy collapses to PNP[log n]. (v) If $S_{2}^{2}$ proves NP ⊆ P/poly then $S_{2}^{2}$ proves that the Polynomial Hierarchy (...) collapses to PNP. Motivated by these results we introduce a new concept in proof complexity: proof systems with advice, and we make some initial observations about them. (shrink)

We introduce a second-order system V1-Horn of bounded arithmetic formalizing polynomial-time reasoning, based on Grädel's 35) second-order Horn characterization of P. Our system has comprehension over P predicates , and only finitely many function symbols. Other systems of polynomial-time reasoning either allow induction on NP predicates , and hence are more powerful than our system , or use Cobham's theorem to introduce function symbols for all polynomial-time functions . We prove that our system is equivalent to QPV and Zambella's P-def. (...) Using our techniques, we also show that V1-Horn is finitely axiomatizable, and, as a corollary, that the class of Σ1b consequences of S21 is finitely axiomatizable as well, thus answering an open question. (shrink)

Dynamic ordinal analysis is ordinal analysis for weak arithmetics like fragments of bounded arithmetic. In this paper we will define dynamic ordinals – they will be sets of number theoretic functions measuring the amount of sΠ b 1(X) order induction available in a theory. We will compare order induction to successor induction over weak theories. We will compute dynamic ordinals of the bounded arithmetic theories sΣ b n (X)−L m IND for m=n and m=n+1, n≥0. Different dynamic ordinals lead to (...) separation. In this way we will obtain several separation results between these relativized theories. We will generalize our results to further languages extending the language of bounded arithmetic. (shrink)

We bring together some facts about the weak pigeonhole principle from bounded arithmetic, complexity theory, cryptography and abstract model theory. We characterize the models of arithmetic in which WPHP fails as those which are determined by an initial segment and prove a conditional separation result in bounded arithmetic, that PV + lies strictly between PV and S21 in strength, assuming that the cryptosystem RSA is secure.

Using nonstandard methods we construct a model of an induction scheme called inside a "resource" of the form is a Turing machine of code is calculated in less than , where means the length of the binary expansion of and are nonstandard parameters in a model of . As a consequence we obtain a model theoretic proof of a witnessing theorem for this theory by functions computable in time , a result first obtained by Buss, Krajícek, and Takeuti using proof (...) theory. (shrink)

The complexity class of [Formula: see text]-polynomial local search problems is introduced and is used to give new witnessing theorems for fragments of bounded arithmetic. For 1 ≤ i ≤ k + 1, the [Formula: see text]-definable functions of [Formula: see text] are characterized in terms of [Formula: see text]-PLS problems. These [Formula: see text]-PLS problems can be defined in a weak base theory such as [Formula: see text], and proved to be total in [Formula: see text]. Furthermore, the [Formula: (...) see text]-PLS definitions can be skolemized with simple polynomial time functions, and the witnessing theorem itself can be formalized, and skolemized, in a weak base theory. We introduce a new [Formula: see text]-principle that is conjectured to separate [Formula: see text] and [Formula: see text]. (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.