We investigate the computational complexity of deciding whether a given inference rule is admissible for some modal and superintuitionistic logics. We state a broad condition under which the admissibility problem is coNEXP-hard. We also show that admissibility in several well-known systems (including GL, S4, and IPC) is in coNE, thus obtaining a sharp complexity estimate for admissibility in these systems.

We develop canonical rules capable of axiomatizing all systems of multiple-conclusion rules over K4 or IPC, by extension of the method of canonical formulas by Zakharyaschev [37]. We use the framework to give an alternative proof of the known analysis of admissible rules in basic transitive logics, which additionally yields the following dichotomy: any canonical rule is either admissible in the logic, or it is equivalent to an assumption-free rule. Other applications of canonical rules include a generalization of the Blok–Esakia (...) theorem and the theory of modal companions to systems of multiple-conclusion rules or (finitary structural global) consequence relations, and a characterization of splittings in the lattices of consequence relations over monomodal or superintuitionistic logics with the finite model property. (shrink)

We show that IPC, K4, GL, and S4, as well as all logics inheriting their admissible rules, have independent bases of admissible rules.

We show that \, the basic theory of bounded arithmetic corresponding to the complexity class \, proves the \ axiom expressing the totality of iterated multiplication satisfying its recursive definition, by formalizing a suitable version of the \ iterated multiplication algorithm by Hesse, Allender, and Barrington. As a consequence, \ can also prove the integer division axiom, and the \-translation of induction and minimization for sharply bounded formulas. Similar consequences hold for the related theories \ and \. As a side (...) result, we also prove that there is a well-behaved \ definition of modular powering in \\). (shrink)

We study the notion of conservative translation between logics introduced by (Feitosa & D’Ottaviano2001). We show that classical propositional logic (CPC) is universal in the sense that every finitary consequence relation over a countable set of formulas can be conservatively translated into CPC. The translation is computable if the consequence relation is decidable. More generally, we show that one can take instead of CPC a broad class of logics (extensions of a certain fragment of full Lambek calculus FL) including most (...) nonclassical logics studied in the literature, hence in a sense, (almost) any two reasonable deductive systems can be conservatively translated into each other. We also provide some counterexamples, in particular the paraconsistent logic LP is not universal. (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)

The purpose of this paper is to clarify the relationship between various conditions implying essential undecidability: our main result is that there exists a theory T in which all partially recursive functions are representable, yet T does not interpret Robinson’s theory R. To this end, we borrow tools from model theory — specifically, we investigate model-theoretic properties of the model completion of the empty theory in a language with function symbols. We obtain a certain characterization of ∃∀ theories interpretable in (...) existential theories in the process. (shrink)

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

We investigate the substitution Frege () proof system and its relationship to extended Frege () in the context of modal and superintuitionistic propositional logics. We show that is p-equivalent to tree-like , and we develop a “normal form” for -proofs. We establish connections between for a logic L, and for certain bimodal expansions of L.We then turn attention to specific families of modal and si logics. We prove p-equivalence of and for all extensions of , all tabular logics, all logics (...) of finite depth and width, and typical examples of logics of finite width and infinite depth. In most cases, we actually show an equivalence with the usual system for classical logic with respect to a naturally defined translation.On the other hand, we establish exponential speed-up of over for all modal and si logics of infinite branching, extending recent lower bounds by P. Hrubeš. We develop a model-theoretical characterization of maximal logics of infinite branching to prove this result. (shrink)

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 develop an arithmetical theory and its variant , corresponding to “slightly nonuniform” . Our theories sit between and , and allow evaluation of log-depth bounded fan-in circuits under limited conditions. Propositional translations of -formulas provable in admit L-uniform polynomial-size Frege proofs.

By a well-known result of Cook and Reckhow [S.A. Cook, R.A. Reckhow, The relative efficiency of propositional proof systems, Journal of Symbolic Logic 44 36–50; R.A. Reckhow, On the lengths of proofs in the propositional calculus, Ph.D. Thesis, Department of Computer Science, University of Toronto, 1976], all Frege systems for the classical propositional calculus are polynomially equivalent. Mints and Kojevnikov [G. Mints, A. Kojevnikov, Intuitionistic Frege systems are polynomially equivalent, Zapiski Nauchnyh Seminarov POMI 316 129–146] have recently shown p-equivalence of (...) Frege systems for the intuitionistic propositional calculus in the standard language, building on a description of admissible rules of IPC by Iemhoff [R. Iemhoff, On the admissible rules of intuitionistic propositional logic, Journal of Symbolic Logic 66 281–294]. We prove a similar result for an infinite family of normal modal logics, including K4, GL, S4, and. (shrink)

We prove that all axiomatic extensions of the full Lambek calculus with exchange can be axiomatized by formulas on the level of the substructural hierarchy.

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 elementary arithmetic operations +,·,≤\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${+,\cdot,\le}$$\end{document} on integers are well-known to be computable in the weak complexity class TC0, and it is a basic question what properties of these operations can be proved using only TC0-computable objects, i.e., in a theory of bounded arithmetic corresponding to TC0. We will show that the theory VTC0 extended with an axiom postulating the totality of iterated multiplication proves induction for quantifier-free formulas in the language ⟨+,·,≤⟩\documentclass[12pt]{minimal} (...) \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\langle{+,\cdot,\le}\rangle}$$\end{document}, and more generally, minimization for Σ0b\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma_{0}^{b}}$$\end{document} formulas in the language of Buss’s S2. (shrink)

We show that the universally axiomatized, induction-free theory equation image is a sequential theory in the sense of Pudlák's 5, in contrast to the closely related Robinson's arithmetic.

We formalize the construction of Paterson’s variant of the Ajtai–Komlós–Szemerédi sorting network of logarithmic depth in the bounded arithmetical theory , under the assumption of the existence of suitable expander graphs. We derive a conditional p-simulation of the propositional sequent calculus in the monotone sequent calculus.

D’Aquino et al. (J Symb Log 75(1):1–11, 2010) have recently shown that every real-closed field with an integer part satisfying the arithmetic theory IΣ4 is recursively saturated, and that this theorem fails if IΣ4 is replaced by IΔ0. We prove that the theorem holds if IΣ4 is replaced by weak subtheories of Buss’ bounded arithmetic: PV or \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^b_1-IND^{|x|_k}}$$\end{document}. It also holds for IΔ0 (and even its subtheory IE2) under a rather mild (...) assumption on cofinality. On the other hand, it fails for the extension of IOpen by an axiom expressing the Bézout property, even under the same assumption on cofinality. (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 introduce a nonstandard arithmetic $NQA^-$ based on the theory developed by R. Chuaqui and P. Suppes in [2] (we will denote it by $NQA^+$ ), with a weakened external open minimization schema. A finitary consistency proof for $NQA^-$ formalizable in PRA is presented. We also show interesting facts about the strength of the theories $NQA^-$ and $NQA^+$ ; $NQA^-$ is mutually interpretable with $I\Delta_0 + EXP$ , and on the other hand, $NQA^+$ interprets the theories IΣ1 and $WKL_0$.

We investigate the provability of some properties of abelian groups and quadratic residues in variants of bounded arithmetic. Specifically, we show that the structure theorem for finite abelian groups is provable in S22 + iWPHP, and use it to derive Fermat's little theorem and Euler's criterion for the Legendre symbol in S22 + iWPHP extended by the pigeonhole principle PHP. We prove the quadratic reciprocity theorem in the arithmetic theories T20 + Count2 and I Δ0 + Count2 with modulo-2 counting (...) principles. (shrink)

We prove that (additive) ordered group reducts of nonstandard models of the bounded arithmetical theory are recursively saturated in a rich language with predicates expressing the integers, rationals, and logarithmically bounded numbers. Combined with our previous results on the construction of the real exponential function on completions of models of, we show that every countable model of is an exponential integer part of a real‐closed exponential field.

Grzegorczyk's modal logic corresponds to the class of upwards well-founded partially ordered Kripke frames, however all known proofs of this fact utilize some form of the Axiom of Choice; G. Boolos asked in [1], whether it is provable in plain ZF. We answer his question negatively: Grz corresponds to a class of frames, which does not provably coincide with upwards well-founded posets in ZF alone.

Atserias, Galesi, and Pudlák have shown that the monotone sequent calculus MLK quasipolynomially simulates proofs of monotone sequents in the full sequent calculus LK . We generalize the simulation to the fragment MCLK of LK which can prove arbitrary sequents, but restricts cut-formulas to be monotone. We also show that MLK as a refutation system for CNFs quasipolynomially simulates LK.

We present a description of rigid models of Presburger arithmetic (i.e., ‐groups). In particular, we show that Presburger arithmetic has rigid models of all infinite cardinalities up to the continuum, but no larger.

We show that for any, the structure of sets that are hereditarily of size at most k is decidable. We provide a transparent complete axiomatization of its theory, a quantifier elimination result, and tight bounds on its computational complexity. This stands in stark contrast to the structure of hereditarily finite sets, which is well known to be bi‐interpretable with the standard model of arithmetic.

We show that the quantified propositional proof systems Gi are polynomially equivalent to their restricted versions that require all cut formulas to be prenex Σqi . Previously this was known only for the treelike systems G*i. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.

We show that VTC0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ VTC ^0$$\end{document}, the basic theory of bounded arithmetic corresponding to the complexity class TC0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {TC}^0$$\end{document}, proves the IMUL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ IMUL $$\end{document} axiom expressing the totality of iterated multiplication satisfying its recursive definition, by formalizing a suitable version of the TC0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {TC}^0$$\end{document} iterated (...) multiplication algorithm by Hesse, Allender, and Barrington. As a consequence, VTC0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ VTC ^0$$\end{document} can also prove the integer division axiom, and the RSUV\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ RSUV $$\end{document}-translation of induction and minimization for sharply bounded formulas. Similar consequences hold for the related theories Δ1b-CR\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta ^b_1\text{- } CR $$\end{document} and C20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C^0_2$$\end{document}. As a side result, we also prove that there is a well-behaved Δ0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta _0$$\end{document} definition of modular powering in IΔ0+WPHP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I\Delta _0+ WPHP $$\end{document}. (shrink)