This paper obtains lower and upper bounds for the number of alternations of bounded quantifiers needed to express all formulas in certain ordered Abelian groups admitting elimination of unbounded quantifiers. The paper also establishes model-theoretic tests for equivalence to a formula with a given number of alternations of bounded quantifiers.

This book presents an up-to-date, unified treatment of research in bounded arithmetic and complexity of propositional logic, with emphasis on independence proofs and lower bound proofs. The author discusses the deep connections between logic and complexity theory and lists a number of intriguing open problems. An introduction to the basics of logic and complexity theory is followed by discussion of important results in propositional proof systems and systems of bounded arithmetic. More advanced topics are then treated, including (...) polynomial simulations and conservativity results, various witnessing theorems, the translation of bounded formulas (and their proofs) into propositional ones, the method of random partial restrictions and its applications, direct independence proofs, complete systems of partial relations, lower bounds to the size of constant-depth propositional proofs, the method of Boolean valuations, the issue of hard tautologies and optimal proof systems, combinatorics and complexity theory within bounded arithmetic, and relations to complexity issues of predicate calculus. Students and researchers in mathematical logic and complexity theory will find this comprehensive treatment an excellent guide to this expanding interdisciplinary area. (shrink)

We study the computational complexity of the universal and quasi-equational theories of classes of bounded distributive lattices with a negation operation, i.e., a unary operation satisfying a subset of the properties of the Boolean negation. The upper bounds are obtained through the use of partial algebras. The lower bounds are either inherited from the equational theory of bounded distributive lattices or obtained through a reduction of a global satisfiability problem for a suitable system of propositional modal logic.

The paper considers a commonly used axiomatization of the classical propositional logic and studies how different axiom schemata in this system contribute to proof complexity of the logic. The existence of a polynomial bound on proof complexity of every statement provable in this logic is a well-known open question.The axiomatization consists of three schemata. We show that any statement provable using unrestricted number of axioms from the first of the three schemata and polynomially-bounded in size set of axioms (...) from the other schemata, has a polynomially-bounded proof complexity. In addition, it is also established, that any statement, provable using unrestricted number of axioms from the remaining two schemata and polynomially-bounded in size set of axioms from the first scheme, also has a polynomially-bounded proof complexity. (shrink)

In this paper, we study bounded versions of some model-theoretic notions and results. We apply these results to the context of models of bounded arithmetic theories as well as some related complexity questions. As an example, we show that if the theory $\rm S_2 ^1(PV)$ has bounded model companion then $\rm NP=coNP$. We also study bounded versions of some other related notions such as Stone topology.

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)

Let μ be a universal lower enumerable semi-measure . Any computable upper bound for μ can be effectively separated from zero with a constant . Computable positive lower bounds for μ can be nontrivial and allow one to construct natural examples of hypersimple sets.

This research explores the relationship between the bounded in-degree and out-degree of an argumentation framework and the computational complexity of the problems of Credulous Acceptance ( CredA ) and Skeptical Acceptance ( SkepA ) under preferred extensions. Researchers have studied the complexity of these problems when the in-degree [Formula: see text] and out-degree [Formula: see text] of the arguments are restricted to [Formula: see text]. Despite this restriction, the computational complexities of CredA and SkepA persist. Based on these (...) results, we presents new results that provide deeper insights into the impact of additional constraints on the argumentation framework. Specifically, we show that when “[Formula: see text]” or “[Formula: see text]” is restricted to [Formula: see text], both problems CredA and SkepA can be solved in polynomial time. Subsequently, we impose additional constraints on the argumentation framework by analyzing the quantities “[Formula: see text],” “[Formula: see text],” and “[Formula: see text].” For an argumentation framework [Formula: see text] and all arguments “[Formula: see text]” of [Formula: see text], the parameter “[Formula: see text]” indicates the maximum number of attackers that any argument “[Formula: see text]” can have among all those that are not attacked by “[Formula: see text]” [Formula: see text], “[Formula: see text]” indicates the maximum number of arguments that any argument “[Formula: see text]” attacks among all those that do not attack “[Formula: see text]”, and “[Formula: see text]” denotes the maximum number of arguments that any argument “[Formula: see text]” attacks among those that attack “[Formula: see text]”. Surprisingly, even when all these quantities are restricted to [Formula: see text], the computational complexity of CredA persists. Furthermore, we explore the influence of symmetric attacks by fixing “[Formula: see text]” to zero, while setting “[Formula: see text]” and “[Formula: see text]” to [Formula: see text]. Remarkably, the complexity of CredA persists under this restriction as well. (shrink)

We show that for every computable limit ordinal α, there is a computable structure A that is $\Delta _\alpha ^0 $ categorical, but not relatively $\Delta _\alpha ^0 $ categorical (equivalently. it does not have a formally $\Sigma _\alpha ^0 $ Scott family). We also show that for every computable limit ordinal a, there is a computable structure A with an additional relation R that is intrinsically $\Sigma _\alpha ^0 $ on A. but not relatively intrinsically $\Sigma _\alpha ^0 $ (...) on A (equivalently, it is not definable by a computable $\Sigma _\alpha $ formula with finitely many parameters). Earlier results in [7], [10], and [8] establish the same facts for computable successor ordinals α. (shrink)

The Kolmogorov complexity of a finite binary string is the length of the shortest description of the string. This gives rise to some ‘standard’ lowness notions for reals: A isK-trivial if its initial segments have the lowest possible complexity and A is low forKif using A as an oracle does not decrease the complexity of strings by more than a constant factor. We weaken these notions by requiring the defining inequalities to hold only up to all${\rm{\Delta }}_2^0$orders, (...) and call the new notions${\rm{\Delta }}_2^0$-bounded K-trivialand${\rm{\Delta }}_2^0$-bounded low for K. Several of the ‘nice’ properties ofK-triviality are lost with this weakening. For instance, the new weaker definitions both give uncountable set of reals. In this paper we show that the weaker definitions are no longer equivalent, and that the${\rm{\Delta }}_2^0$-boundedK-trivials are cofinal in the Turing degrees. We then compare them to other previously studied weakenings, namelyinfinitely-often K-trivialityandweak lowness for K. We show that${\rm{\Delta }}_2^0$-boundedK-trivial implies infinitely-oftenK-trivial, but no implication holds between${\rm{\Delta }}_2^0$-bounded low forKand weakly low forK. (shrink)

For any n, we construct a model of in which each formula is equivalent to an formula.

We consider the Lambek calculus, or noncommutative multiplicative intuitionistic linear logic, extended with iteration, or Kleene star, axiomatised by means of an$\omega $-rule, and prove that the derivability problem in this calculus is$\Pi _1^0$-hard. This solves a problem left open by Buszkowski (2007), who obtained the same complexity bound for infinitary action logic, which additionally includes additive conjunction and disjunction. As a by-product, we prove that any context-free language without the empty word can be generated by a Lambek grammar (...) with unique type assignment, without Lambek’s nonemptiness restriction imposed (cf. Safiullin, 2007). (shrink)

If we express our knowledge in sentences, we will find that these sentences are linked in complex patterns governed by our observations and our inferences from these observations. These inferences are to a large extent driven by logical rules. We ask whether the structure logic imposes on our knowledge restricts what we forget and what we remember. The model is a two period S5 logic. In this logic, we propose a memory loss operator: the agent forgets a sentence pif and (...) only if he knows pat time 1 and he does not know pat time 2. Equipped with the operator, we prove theorems on the relation between knowledge and memory loss. The main results point to classes of formulas that an agent cannot forget, and classes of formulas he must forget. A desirable feature is that most results hold in the S4 logic. The results illustrate bounds to memory loss, and thus to bounded rationality. We apply the model to single-agent conventions: conventions made between an agent and himself. (shrink)

I present evidence for a systematic complexity-coherence tradeoff in cognition. I show how feasible strategies for increasing cognitive complexity along three dimensions come at the expense of a heightened vulnerability to incoherence. I discuss two normative implications of the complexity-coherence tradeoff: a novel challenge to coherence-based theories of bounded rationality and a new strategy for vindicating the rationality of seemingly irrational cognitions. I also discuss how the complexity-coherence tradeoff sharpens recent descriptive challenges to dual process theories (...) of cognition. (shrink)

We derive the exact inefficiency upper bounds of the multiclass C-Logit stochastic user equilibrium in a transportation network. All travelers are classified on the basis of different values of time into M classes. The multiclass CL-SUE model gives a more realistic path choice probability in comparison with the logit-based stochastic user equilibrium model by considering the overlapping effects between paths. To find efficiency loss upper bounds of the multiclass CL-SUE, two equivalent variational inequalities for the multiclass CL-SUE model, (...) i.e., time-based variational inequality and monetary-based VI, are formulated. We give four different methods to define the inefficiency of the multiclass CL-SUE, i.e., to compare multiclass CL-SUE with multiclass system optimum, or to compare multiclass CL-SUE with multiclass C-Logit stochastic system optimum, under the time-based criterion and the monetary-based criterion, respectively. We further investigate the effects of various parameters which include the degree of path overlapping, the network complexity, degree of traffic congestion, the VOT of user classes, the network familiarity, and the total demand on the inefficiency bounds. (shrink)

We introduce frame-equivalence games tailored for reasoning about the size, modal depth, number of occurrences of symbols and number of different propositional variables of modal formulae defining a given frame property. Using these games, we prove lower bounds on the above measures for a number of well-known modal axioms; what is more, for some of the axioms, we show that they are optimal among the formulae defining the respective class of frames.

We introduce the equational notion of a monadic bounded algebra (MBA), intended to capture algebraic properties of bounded quantification. The variety of all MBA's is shown to be generated by certain algebras of two-valued propositional functions that correspond to models of monadic free logic with an existence predicate. Every MBA is a subdirect product of such functional algebras, a fact that can be seen as an algebraic counterpart to semantic completeness for monadic free logic. The analysis involves the representation of (...) MBA's as powerset algebras of certain directed graphs with a set of "marked" points. It is shown that there are only countably many varieties of MBA's, all are generated by their finite members, and all have finite equational axiomatisations classifying them into fourteen kinds of variety. The universal theory of each variety is decidable. Finitely generated MBA's are shown to be finite, with the free algebra on r generators having exactly $2^{3.2^{r.} } ^{2^{{\rm{2}}^{{\rm{r - 1}}} } } $ elements. An explicit procedure is given for constructing this freely generated algebra as the powerset algebra of a certain marked graph determined by the number r. (shrink)

We define theories of bounded arithmetic, whose definable functions and relations are exactly those in certain complexity classes. Based on a recursion-theoretic characterization of NC in Clote , the first-order theory TNC, whose principal axiom scheme is a form of short induction on notation for nondeterministic polynomial-time computable relations, has the property that those functions having nondeterministic polynomial-time graph Θ such that TNC x y Θ are exactly the functions in NC, computable on a parallel random-access machine in polylogarithmic (...) parallel time with a polynomial number of processors.0 We then define three theories of weak second-order arithmetic which respectively characterize relations in the classes of alternating logarithmic time, logspace and nondeterministic logspace. (shrink)

Worst case complexity analyses of algorithms are sometimes held to be less informative about the real difficulty of computation than are expected complexity analyses. We show that the two most common representations of problem solving in cognitive science each admit aigorithms that have constant expected complexity, and for one of these representations we obtain constant expected complexity bounds under a variety of probability measures.

The finite age of the universe and the existence of cosmological horizons provides a strong argument that the observable universe represents a finite causal region with finite material and informational resources. A similar conclusion follows from the holographic principle. In this paper I address the question of whether the cosmological information bound has implications for fundamental physics. Orthodox physics is based on Platonism: the laws are treated as infinitely precise, perfect, immutable mathematical relationships that transcend the physical universe and remain (...) totally unchanged by physical processes, however extreme. If instead the laws of physics are regarded as akin to computer software, with the physical universe as the corresponding hardware, then the finite computational capacity of the universe imposes a fundamental limit on the precision of the laws and the specifiability of physical states. That limit depends on the age of the universe. I examine how the imprecision of the laws impacts on the evolution of highly entangled states and on the problem of dark energy. (shrink)

"Put together one of the world's best science writers with one of the universe's most fascinating subjects and you are bound to produce a wonderful book.... The subject of complexity is vital and controversial. This book is important and beautifully done."--Stephen Jay Gould "[Complexity] is that curious mix of complication and organization that we find throughout the natural and human worlds: the workings of a cell, the structure of the brain, the behavior of the stock market, the shifts (...) of political power.... It is time science... thinks about meaning as well as counting information.... This is the core of the complexity manifesto. Read it, think about it... but don't ignore it."--Ian Stewart, "Nature" This second edition has been brought up to date with an essay entitled "On the Edge in the Business World" and an interview with John Holland, author of "Emergence: From Chaos to Order.". (shrink)

In this paper we prove a bounded translation of intuitionistic propositional logic into basic propositional logic. Our new theorem, compared with the translation theorem in [1], has the advantage that it gives an effective bound on the translation, depending on the complexity of formulas.