On the Computational Complexity of the Numerically Definite Syllogistic and Related Logics
Ian E. Pratt-Hartmann · Bulletin of Symbolic Logic · 2008
Abstract Thenumerically definite syllogisticis the fragment of English obtained by extending the language of the classical syllogism with numerical quantifiers. Thenumerically definite relational syllogisticis 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.