We consider the following problem: Given a proof of the Skolemization of a formula F, what is the length of the shortest proof of F? For the restriction of this question to cut-free proofs we prove corresponding exponential upper and lower bounds.

Propositional proof complexity is the study of the sizes of propositional proofs, and more generally, the resources necessary to certify propositional tautologies. Questions about proof sizes have connections with computational complexity, theories of arithmetic, and satisfiability algorithms. This is article includes a broad survey of the field, and a technical exposition of some recently developed techniques for proving lower bounds on proof sizes.

Default logic is one of the most popular and successful formalisms for non-monotonic reasoning. In 2002, Bonatti and Olivetti introduced several sequent calculi for credulous and skeptical reasoning in propositional default logic. In this paper we examine these calculi from a proof-complexity perspective. In particular, we show that the calculus for credulous reasoning obeys almost the same bounds on the proof size as Gentzen’s system LK. Hence proving lower bounds for credulous reasoning will be as hard as proving lower (...) bounds for LK. On the other hand, we show an exponential lower bound to the proof size in Bonatti and Olivetti’s enhanced calculus for skeptical default reasoning. (shrink)

The length of resolution proofs is investigated, relative to the model-theoretic measure of Herband complexity. A concept of resolution deduction is introduced which is somewhat more general than the classical concepts. It is shown that proof complexity is exponential in terms of Herband complexity and that this bound is tight. The concept of R-deduction is extended to FR-deduction, where, besides resolution, a function introduction rule is allowed. As an example, consider the clause P Q: conclude P) (...) Q, where a, f are new function symbols extending Herbrand's universe. P ()Q from Q) and Skolemization). By modification of a construction of Statman it is shown that FR-deductions may be nonelementarily shorter than R-deductions . Finally it is proved that FR-deduction has weaker effects only if clausal logic is restricted to Horn logic. (shrink)

Propositional proof complexity is the study of the sizes of propositional proofs, and more generally, the resources necessary to certify propositional tautologies. Questions about proof sizes have connections with computational complexity, theories of arithmetic, and satisfiability algorithms. This is article includes a broad survey of the field, and a technical exposition of some recently developed techniques for proving lower bounds on proof sizes.

This book is dedicated to the work of Alasdair Urquhart. The book starts out with an introduction to and an overview of Urquhart’s work, and an autobiographical essay by Urquhart. This introductory section is followed by papers on algebraic logic and lattice theory, papers on the complexity of proofs, and papers on philosophical logic and history of logic. The final section of the book contains a response to the papers by Urquhart. Alasdair Urquhart has made extremely important contributions (...) to a variety of fields in logic. He produced some of the earliest work on the semantics of relevant logic. He provided the undecidability of the logics R and E, as well as some of their close neighbors. He proved that interpolation fails in some of those systems. Urquhart has done very important work in complexity theory, both about the complexity of proofs in classical and some nonclassical logics. In pure algebra, he has produced a representation theorem for lattices and some rather beautiful duality theorems. In addition, he has done important work in the history of logic, especially on Bertrand Russell, including editing Volume four of Russell’s Collected Papers. (shrink)

We introduce two versions of proof systems dealing with systems of inequalities: Positivstellensatz refutations and Positivstellensatz calculus. For both systems we prove the lower bounds on degrees and lengths of derivations for the example due to Lazard, Mora and Philippon. These bounds are sharp, as well as they are for the Nullstellensatz refutations and for the polynomial calculus. The bounds demonstrate a gap between the Null- and Positivstellensatz refutations on one hand, and the polynomial calculus and Positivstellensatz calculus on the (...) other. (shrink)

We prove that for sufficiently large N, there are tautologies of size O that require proofs containing Ω lines in axiomatic systems of propositional logic based on axioms and the rule of substitution for single variables. These tautologies have proofs with O lines in systems with the multiple substitution rule.

The essential structure of proofs is proposed as the basis for a measure of complexity of formulas in FOL. The motivating idea was the recognition that distinct theorems can have the same derivation modulo some non essential details. Hence the difficulty in proving them is identical and so their complexity should be the same. We propose a notion of complexity of formulas capturing this property. With this purpose, we introduce the notions of schema calculus, schema derivation (...) and description complexity of a schema formula. Based on these concepts we prove general robustness results that relate the complexity of introducing a logical constructor with the complexity of the component schema formulas as well as the complexity of a schema formula across different schema calculi. (shrink)

We introduce three formal theories of increasing strength for linear algebra in order to study the complexity of the concepts needed to prove the basic theorems of the subject. We give what is apparently the first feasible proofs of the Cayley–Hamilton theorem and other properties of the determinant, and study the propositional proof complexity of matrix identities such as AB=I→BA=I.

The undecidability of first-order logic implies that there is no computable bound on the length of shortest proofs of valid sentences of first-order logic. Some valid sentences can only have quite long proofs. How hard is it to prove such "hard" valid sentences? The polynomial time tractability of this problem would imply the fixed-parameter tractability of the parameterized problem that, given a natural number n in unary as input and a first-order sentence φ as parameter, asks whether φ (...) has a proof of length ≤ n. As the underlying classical problem has been considered by Gödel we denote this problem by p-Gödel. We show that p-Gödel is not fixed-parameter tractable if DTIME(h O(1) ) ≠ NTIME(h O(1) ) for all time constructible and increasing functions h. Moreover we analyze the complexity of the construction problem associated with p-Gödel. (shrink)

A new approach to defining complexity of propositional formulas and proofs is suggested. Instead of measuring the size of these syntactical structures in the propositional language, the article suggests to define the complexity by the size of external descriptions of such constructions. The main result is a lower bound on proof complexity with respect to this new definition of complexity.

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)

Let g be a map defined as the Nisan–Wigderson generator but based on an NP ∩ coNP -function f. Any string b outside the range of g determines a propositional tautology τb expressing this fact. Razborov [27] has conjectured that if f is hard on average for P/poly then these tautologies have no polynomial size proofs in the Extended Frege system EF. We consider a more general Statement that the tautologies have no polynomial size proofs in any propositional (...) proof system. This is equivalent to the statement that the complement of the range of g contains no infinite NP set. We prove that Statement is consistent with Cook' s theory PV and, in fact, with the true universal theory T PV in the language of PV. If PV in this consistency statement could be extended to "a bit" stronger theory then Razborov's conjecture would follow, and if TPV could be added too then Statement would follow. We discuss this problem in some detail, pointing out a certain form of reflection principle for propositional logic, and we introduce a related feasible disjunction property of proof systems. (shrink)

This paper shows how proof nets can be used to formalize the notion of incomplete dependency used in psycholinguistic theories of the unacceptability of center embedded constructions. Such theories of human language processing can usually be restated in terms of geometrical constraints on proof nets. The paper ends with a discussion of the relationship between these constraints and incremental semantic interpretation.

We consider the problem about the length of proofs of the sentences $\operatorname{Con}_S(\underline{n})$ saying that there is no proof of contradiction in S whose length is ≤ n. We show the relation of this problem to some problems about propositional proof systems.

This paper considers the computational complexity of the disjunction and existential properties of intuitionistic logic. We prove that the disjunction property holds feasibly for intuitionistic propositional logic; i.e., from a proof of A v B, a proof either of A or of B can be found in polynomial time. For intuitionistic predicate logic, we prove superexponential lower bounds for the disjunction property, namely, there is a superexponential lower bound on the time required, given a proof of A v B, (...) to produce one of A and B which is true. In addition, there is superexponential lower bound on the size of terms which fulfill the existential property of intuitionistic predicate logic. There are superexponential upper bounds for these problems, so the lower bounds are essentially optimal. (shrink)

A Ramsey statement denoted \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${n \longrightarrow (k)^2_2}$$\end{document} says that every undirected graph on n vertices contains either a clique or an independent set of size k. Any such valid statement can be encoded into a valid DNF formula RAM(n, k) of size O(nk) and with terms of size \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\left(\begin{smallmatrix}k\\2\end{smallmatrix}\right)}$$\end{document}. Let rk be the minimal n for which the statement holds. We prove that (...) RAM(rk, k) requires exponential size constant depth Frege systems, answering a problem of Krishnamurthy and Moll [15]. As a consequence of Pudlák’s work in bounded arithmetic [19] it is known that there are quasi-polynomial size constant depth Frege proofs of RAM(4k, k), but the proof complexity of these formulas in resolution R or in its extension R(log) is unknown. We define two relativizations of the Ramsey statement that still have quasi-polynomial size constant depth Frege proofs but for which we establish exponential lower bound for R. (shrink)

We study algebras whose elements are relations, and the operations are natural “manipulations” of relations. This area goes back to 140 years ago to works of De Morgan, Peirce, Schröder . Well known examples of algebras of relations are the varieties RCAn of cylindric algebras of n-ary relations, RPEAn of polyadic equality algebras of n-ary relations, and RRA of binary relations with composition. We prove that any axiomatization, say E, of RCAn has to be very complex in the following sense: (...) for every natural number k there is an equation in E containing more than k distinct variables and all the operation symbols, if 2 < n < ω. Completely analogous statement holds for the case n ω. This improves Monk's famous non-finitizability theorem for which we give here a simple proof. We prove analogous nonfinitizability properties of the larger varieties SNrnCAn + k. We prove that the complementation-free subreducts of RCAn do not form a variety. We also investigate the reason for the above “non-finite axiomatizability” behaviour of RCAn. We look at all the possible reducts of RCAn and investigate which are finitely axiomatizable. We obtain several positive results in this direction. Finally, we summarize the results and remaining questions in a figure. We carry through the same programme for RPEAn and for RRA. By looking into the reducts we also investigate what other kinds of natural algebras of relations are possible with more positive behaviour than that of the well known ones. Our investigations have direct consequences for the logical properties of the n-variable fragment Ln of first order logic. The reason for this is that RCAn and RPEAn are the natural algebraic counterparts of Ln while the varieties SNrnCAn + k are in connection with the proof theory of Ln. This paper appears in two parts. The first part contains the non-finite axiomatizability results. The present second part contains finite axiomatizations of some fragments together with a figure summarizing the finite and non-finite axiomatizability results in this area and the problems left open. (shrink)

We study algebras whose elements are relations, and the operations are natural “manipulations” of relations. This area goes back to 140 years ago to works of De Morgan, Peirce, Schröder . Well known examples of algebras of relations are the varieties RCAn of cylindric algebras of n-ary relations, RPEAn of polyadic equality algebras of n-ary relations, and RRA of binary relations with composition. We prove that any axiomatization, say E, of RCAn has to be very complex in the following sense: (...) for every natural number k there is an equation in E containing more than k distinct variables and all the operation symbols, if 2 < n < ω. Completely analogous statement holds for the case n ω. This improves Monk's famous non-finitizability theorem for which we give here a simple proof. We prove analogous nonfinitizability properties of the larger varieties SNrnCAn + k. We prove that the complementation-free subreducts of RCAn do not form a variety. We also investigate the reason for the above “non-finite axiomatizability” behaviour of RCAn. We look at all the possible reducts of RCAn and investigate which are finitely axiomatizable. We obtain several positive results in this direction. Finally, we summarize the results and remaining questions in a figure. We carry through the same programme for RPEAn and for RRA. By looking into the reducts we also investigate what other kinds of natural algebras of relations are possible with more positive behaviour than that of the well known ones. Our investigations have direct consequences for the logical properties of the n-variable fragment Ln of first order logic. The reason for this is that RCAn and RPEAn are the natural algebraic counterparts of Ln while the varieties SNrnCAn + k are in connection with the proof theory of Ln. This paper appears in two parts. The first part contains the non-finite axiomatizability results. The present second part contains finite axiomatizations of some fragments together with a figure summarizing the finite and non-finite axiomatizability results in this area and the problems left open. (shrink)

In his book on fallacies, Hamblin built a very simple system for argumentation in dialogue he called the Why Because System with Questions. In his discussion of this system, he replaced the concept of burden of proof with a simpler concept of initiative, which could be described as something like getting the upper hand as the argumentation moves back and forth in the dialogue between the one party and the other. No doubt he realized that the concept of burden of (...) proof was too complex a matter to be dealt with in the limited scope of his chapter on formal dialogue systems. In this paper is shown how an extended version of Hamblin’s dialogue system provides a nice way of modeling the phenomenon of shifting of burden of proof in a dialogue, yielding a precise way of distinguishing between different kinds of burden of proof, and dealing with fallacies like the argumentum ad ignorantiam. (shrink)

The European Union is making increased efforts to find simpler and more effective ways to function adequately in the eyes of its citizens by using ‘soft law’ instruments such as recommendations. Although they have no legally binding force, recommendations have practical and legal effects occurring partly due to their normative content in which a course of action is prescribed and further supported by arguments intended to persuade the addressees of a political position. Although recommendations function as persuasive instruments due to (...) their argumentation, the characteristics of argumentation and how it is employed to convince the addressee to comply with certain measures have not been investigated at all. The main goal of the paper is to explain how arguments are used by the European Commission when recommending Member States to follow a new course of action. First, we will unravel the justificatory reasons employed by the Commission in order to make Member States comply with new measures and we will show how these reasons are combined into an argumentative pattern : 1–23, 2016; J Argum Context 6: 3–26, 2017). This pattern basically prescribes a course of action to Member States, which is further supported by arguments in which the necessity and advantages of following the proposed course of action are justified. Second, we will explain how and why the way in which the arguments are combined in this complex pattern could be potentially persuasive for the Member States despite the legally non-binding character of recommendations. We will show that the European Commission tries to persuade the Member States to take new measures by evading the burden of proof imposed by the legislative framework. At a more specific level of analysis, we will delve into the implicit premises in the argumentation, which enable us to identify cases of evasion of the burden of proof due to the Commission’s use of implicit starting points which might not be accepted by the Member States. (shrink)

Extending techniques of Dowd and those of Poizat, we study computational complexity of in the case when is a generic oracle, where is a positive integer, and denotes the collection of all -query tautologies with respect to an oracle . We introduce the notion of ceiling-generic oracles, as a generalization of Dowd's notion of -generic oracles to arbitrary finitely testable arithmetical predicates. We study how existence of ceiling-generic oracles affects behavior of a generic oracle, by which we show that (...) is not a subset of is comeager in the Cantor space. Moreover, using ceiling-generic oracles, we present an alternative proof of the fact (Dowd) that the class of all -generic oracles has Lebesgue measure zero. (shrink)

§1. Introduction. The classical propositional calculus has an undeserved reputation among logicians as being essentially trivial. I hope to convince the reader that it presents some of the most challenging and intriguing problems in modern logic. Although the problem of the complexity of propositional proofs is very natural, it has been investigated systematically only since the late 1960s. Interest in the problem arose from two fields connected with computers, automated theorem proving and computational complexity theory. The earliest (...) paper in the subject is a ground-breaking article by Tseitin [62], the published version of a talk given in 1966 at a Leningrad seminar. In the three decades since that talk, substantial progress has been made in determining the relative complexity of proof systems, and in proving strong lower bounds for some restricted proof systems. However, major problems remain to challenge researchers. The present paper provides a survey of the field, and of some of the techniques that have proved successful in deriving lower bounds on the complexity of proofs. A major area only touched upon here is the proof theory of bounded arithmetic and its relation to the complexity of propositional proofs. The reader is referred to the book by Buss [10] for background in bounded arithmetic. The forthcoming book by Krajíček [40] also gives a good introduction to bounded arithmetic, as well as covering most of the basic results in complexity of propositional proofs. (shrink)

§1. Introduction. The classical propositional calculus has an undeserved reputation among logicians as being essentially trivial. I hope to convince the reader that it presents some of the most challenging and intriguing problems in modern logic. Although the problem of the complexity of propositional proofs is very natural, it has been investigated systematically only since the late 1960s. Interest in the problem arose from two fields connected with computers, automated theorem proving and computational complexity theory. The earliest (...) paper in the subject is a ground-breaking article by Tseitin [62], the published version of a talk given in 1966 at a Leningrad seminar. In the three decades since that talk, substantial progress has been made in determining the relative complexity of proof systems, and in proving strong lower bounds for some restricted proof systems. However, major problems remain to challenge researchers. The present paper provides a survey of the field, and of some of the techniques that have proved successful in deriving lower bounds on the complexity of proofs. A major area only touched upon here is the proof theory of bounded arithmetic and its relation to the complexity of propositional proofs. The reader is referred to the book by Buss [10] for background in bounded arithmetic. The forthcoming book by Krajíček [40] also gives a good introduction to bounded arithmetic, as well as covering most of the basic results in complexity of propositional proofs. (shrink)

The main result of the present paper is that the variable-free fragment of logic K*, the logic with a single K-style modality and its “reflexive and transitive closure,” is EXPTIMEcomplete. It is then shown that this immediately gives EXPTIME-completeness of variable-free fragments of a number of known EXPTIME-complete logics. Our proof contains a general idea of how to construct a polynomial-time reduction of a propositional logic to its n-variable—and even, in the cases of K*, PDL, CTL, ATL, and some others, (...) variable-free—fragments. Complexity of countermodels for such fragments is considered. (shrink)

The method of analytic tableaux is employed in many introductory texts and has also been used quite extensively as a basis for automated theorem proving. In this paper, we discuss the complexity of the system as a method for refuting contradictory sets of clauses, and resolve several open questions. We discuss the three forms of analytic tableaux: clausal tableaux, generalized clausal tableaux, and binary tableaux. We resolve the relative complexity of these three forms of tableaux proofs and (...) also resolve the relative complexity of analytic tableaux versus resolution. We show that there is a quasi-polynomial simulation of tree resolution by analytic tableaux; this simulation is close to optimal, since we give a matching lower bound that is tight to within a polynomial. (shrink)

The goal of this paper is to announce there is a single orbit of the c.e. sets with inclusion, ε, such that the question of membership in this orbit is ${\Sigma _1^1 }$ -complete. This result and proof have a number of nice corollaries: the Scott rank of ε is $\omega _1^{{\rm{CK}}}$ + 1; not all orbits are elementarily definable; there is no arithmetic description of all orbits of ε; for all finite α ≥ 9, there is a properly $\Delta (...) _\alpha ^0 $ orbit (from the proof). (shrink)

Smullyan in [Smu61] identified the recursion theoretic essence of incompleteness results such as Gödel's first incompleteness theorem and Rosser's theorem. Smullyan showed that, for sufficiently complex theories, the collection of provable formulae and the collection of refutable formulae are effectively inseparable—where formulae and their Gödel numbers are identified. This paper gives a similar treatment for proof speed-up. We say that a formal system S1is speedable over another system S0on a set of formulaeAiff, for each recursive functionh, there is a formulaαinAsuch (...) that the length of the shortest proof ofαin S0is larger thanhof the shortest proof ofαin S1. We characterize speedability in terms of the inseparability by r.e. sets of the collection of formulae which are provable in S1but unprovable in S0from the collectionA–where again formulae and their Gödel numbers are identified. We provide precise definitions of proof length, speedability and r.e. inseparability below.We follow the terminology and notation of [Rog87] with borrowings from [Soa87]. Below,ϕis an acceptable numbering of the partial recursive functions [Rog87] andΦa complexity measure associated withϕ[Blu67], [DW83]. (shrink)

Let E be a separable Banach space with separable dual. We show that the operation of subdifferentiation and the inverse operation are Borel from the convex functions on E into the monotone operators on E for the Effros–Borel structures.We also prove that the set of derivatives of differentiable convex functions is coanalytic non-Borel, by using the already known fact that the set of differentiable convex functions is itself coanalytic non-Borel, as proved in Bossard et al. 142).At last, we give a (...) new proof of this latter fact, for reflexive E's, by giving a coanalytic rank on those sets and constructing functions of “high ranks”. This approach, based on an ordinal rank which follows from a construction of trees, is quite different — not so general but actually more constructive — from the previous results of this kind, in Bossard et al. 142) and Godefroy et al. , based on reductions of arbitrary coanalytic or difference of analytic sets to the studied sets. (shrink)

Minimality ranks in the style of Deissler are one way of measuring the structural complexity of minimal extensions of first-order structures. In particular, positive Deissler rank measures the complexity of the injective envelope of a module as an extension of that module. In this paper we solve a problem of the second author by showing that certain injective envelopes have the maximum possible positive Deissler rank complexity. The proof shows that this complexity naturally reflects the internal (...) structure of the injective extension in the form of the levels of the Matlis hierarchy. (shrink)

In the chapter “Information and Content” of their Impossible Worlds, Berto and Jago provide us with a semantic account of information in deductive reasoning such that we have an explanation for why some, but not all, logical deductions are informative. The framework Berto and Jago choose to make sense of the above-mentioned idea is a semantic interpretation of Sequent Calculus rules of inference for classical logic. I shall argue that although Berto and Jago’s idea and framework are hopeful, their definitions (...) do not capture what is intended. This is so because the definitions are solely based on the logical complexity of an argument and they fail to capture the richness of the non- logical content of that argument. Then I will suggest some amendments to address this problem. Finally, I will extend the application of the definitions to first-order logic. It shall be observed that in some classical deductions, applying contraction may lead to hiding some epistemic impossibilities. This happens when formulae which contribute different propositions to the proof get contracted at the quantified level. (shrink)

Presumption is a complex concept in law, affecting the dialogue setting. However, it is not clear how presumptions work in everyday argumentation, in which the concept of “plausible argumentation” seems to encompass all kinds of inferences. By analyzing the legal notion of presumption, it appears that this type of reasoning combines argument schemes with reasoning from ignorance. Presumptive reasoning can be considered a particular form of reasoning, which needs positive or negative evidence to carry a probative weight on the conclusion. (...) For this reason, presumptions shift the burden of providing evidence or explanations onto the interlocutor. The latter can provide new information or fail to do so: whereas in the first case the new information rebuts the presumption, in the second case, the absence of information that the interlocutor could reasonably provide strengthen the conclusion of the presumptive reasoning. In both cases the result of the presumption is to strengthen the conclusion of the reasoning from lack of evidence. As shown in the legal cases, the effect of presumption is to shift the burden of proof to the interlocutor; however, the shift a presumption effects is only the shift of the evidential burden, or the burden of completing the incomplete knowledge from which the conclusion was drawn. The burden of persuasion remains on the proponent of the presumption. On the contrary, reasoning from definition in law is a conclusive proof, and shifts to the other party the burden to prove the contrary. This crucial difference can be applied to everyday argumentation: natural arguments can be divided into dialectical and presumptive arguments, leading to conclusions materially different in strength. -/- . (shrink)

We investigate the initial segment complexity of random reals. Let K denote prefix-free Kolmogorov complexity. A natural measure of the relative randomness of two reals α and β is to compare complexity K and K. It is well-known that a real α is 1-random iff there is a constant c such that for all n, Kn−c. We ask the question, what else can be said about the initial segment complexity of random reals. Thus, we study the (...) fine behaviour of K for random α. Following work of Downey, Hirschfeldt and LaForte, we say that αK β iff there is a constant such that for all n, . We call the equivalence classes under this measure of relative randomness K-degrees. We give proofs that there is a random real α so that lim supn K−K=∞ where Ω is Chaitin's random real. One is based upon work of Solovay, and the other exploits a new idea. Further, based on this new idea, we prove there are uncountably many K-degrees of random reals by proving that μ=0. As a corollary to the proof we can prove there is no largest K-degree. Finally we prove that if n ≠ m then the initial segment complexities of the natural n- and m-random sets and Ω︀) are different. The techniques introduced in this paper have already found a number of other applications. (shrink)

The numerically definite syllogistic is the fragment of English obtained by extending the language of the classical syllogism with numerical quantifiers. The numerically definite relational syllogistic is the fragment of English obtained by extending the numerically definite syllogistic with predicates involving transitive verbs. This paper investigates the computational complexity of the satisfiability problem for these fragments. We show that the satisfiability problem (= finite satisfiability problem) for the numerically definite syllogistic is strongly NP-complete, and that the satisfiability problem (= (...) finite satisfiability problem) for the numerically definite relational syllogistic is NEXPTIME-complete, but perhaps not strongly so. We discuss the related problem of probabilistic (propositional) satisfiability, and thereby demonstrate the incompleteness of some proof-systems that have been proposed for the numerically definite syllogistic. (shrink)

Suppose that Φ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\it \Phi}}$$\end{document} is a consistent sentence. Then there is no Herbrand proof of ¬Φ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\neg {\it \Phi}}$$\end{document}, which means that any Herbrand disjunction made from the prenex form of ¬Φ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\neg {\it \Phi}}$$\end{document} is falsifiable. We show that the problem of finding such a falsifying assignment is hard in the following sense. For every (...) total polynomial search problem R, there exists a consistent Φ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\it \Phi}}$$\end{document} such that finding solutions to R can be reduced to finding a falsifying assignment to an Herbrand disjunction made from ¬Φ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\neg {\it \Phi}}$$\end{document}. It has been conjectured that there are no complete total polynomial search problems. If this conjecture is true, then for every consistent sentence Φ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\it \Phi}}$$\end{document}, there exists a consistent sentence Ψ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Psi}$$\end{document}, such that the search problem associated with Ψ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Psi}$$\end{document} cannot be reduced to the search problem associated with Φ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\it \Phi}}$$\end{document}. (shrink)

In this paper we continue the study of the theories IΔ n+1 (T), initiated in [7]. We focus on the quantifier complexity of these fragments and theirs (non)finite axiomatization. A characterization is obtained for the class of theories such that IΔ n+1 (T) is Π n+2 –axiomatizable. In particular, IΔ n+1 (IΔ n+1 ) gives an axiomatization of Th Π n+2 (IΔ n+1 ) and is not finitely axiomatizable. This fact relates the fragment IΔ n+1 (IΔ n+1 ) to (...) induction rule for Δ n+1 –formulas. Our arguments, involving a construction due to R. Kaye (see [9]), provide proofs of Parsons’ conservativeness theorem (see [16]) and (a weak version) of a result of L.D. Beklemishev on unnested applications of induction rules for Π n+2 and Δ n+1 formulas (see [2]). (shrink)

Mostowski [11] shows that if a structure has a decidable theory, then its weak direct power has one as well; his proof however never produces decision procedures which are elementary recursive. Some very general results are obtained here about the nature of the weak direct power of a structure, which in most cases lead to elementary recursive decision procedures for weak direct powers of structures which themselves have elementary recursive procedures. In particular, it is shown that $\langle N^\ast, +\rangle$ , (...) the weak direct power of $\langle N, +\rangle$ , can be decided in space 2 2 2 cn for some constant c. As corollaries, the same upper bound is obtained for the theory of the structure $\langle N^+, \cdot\rangle$ of positive integers under multiplication, and for the theory of finite abelian groups. Fischer and Rabin [7] have shown that the theory of $\langle N^\ast, +\rangle$ requires time 2 2 2 dn even on nondeterministic Turing machines. (shrink)

Using appropriate notation systems for proofs, cut-reduction can often be rendered feasible on these notations. Explicit bounds can be given. Developing a suitable notation system for Bounded Arithmetic, and applying these bounds, all the known results on definable functions of certain such theories can be reobtained in a uniform way.

We consider three problems concerning alpha conversion of closed terms (combinators). (1) Given a combinator M find the an alpha convert of M with a smallest number of distinct variables. (2) Given two alpha convertible combinators M and N find a shortest alpha conversion of M to N. (3) Given two alpha convertible combinators M and N find an alpha conversion of M to N which uses the smallest number of variables possible along the way. We obtain the following results. (...) (1) There is a polynomial time algorithm for solving problem (1). It is reducible to vertex coloring of chordal graphs. (2) Problem (2) is co-NP complete (in recognition form). The general feedback vertex set problem for digraphs is reducible to problem (2). (3) At most one variable besides those occurring in both M and N is necessary. This appears to be the folklore but the proof is not familiar. A polynomial time algorithm for the alpha conversion of M to N using at most one extra variable is given. There is a tradeoff between solutions to problem (2) and problem (3) which we do not fully understand. (shrink)