A uniform method for proving lower bounds on the computational complexity of logical theories

DOI10.1016/0168-0072(90)90080-LzbMath0705.03017OpenAlexW3037175162MaRDI QIDQ917543

Kevin J. Compton, C. Ward Henson

Publication date: 1990

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0168-0072(90)90080-l

zbMATH Keywords

inseparabilitylower bounds on the computational complexity of logical theories

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15)

Related Items

On iterating linear transformations over recognizable sets of integers, Hyperfinite MV-algebras, Nonconvergence, undecidability, and intractability in asymptotic problems, Probabilities of Sentences about Very Sparse Random Graphs, Inverse monoids: decidability and complexity of algebraic questions., Dominoes and the complexity of subclasses of logical theories, Computational complexity of logical theories of one successor and another unary function, The most nonelementary theory, Algorithmic uses of the Feferman-Vaught theorem, Ehrenfeucht games and ordinal addition, THE RECOGNITION COMPLEXITY OF DECIDABLE THEORIES, Non-elementary lower bound for Propositional Duration Calculus, Model-checking hierarchical structures, The theory of integer multiplication with order restricted to primes is decidable, Simple interpretations among complicated theories, First-order and counting theories ofω-automatic structures, Practical algorithms for MSO model-checking on tree-decomposable graphs, Definability and decidability issues in extensions of the integers with the divisibility predicate, Exact complexity bounds for ordinal addition, Fifty years of the spectrum problem: survey and new results, The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness, An improved lower bound for the elementary theories of trees, Complexity of logical theories involving coprimality, Decidability of the theory of the natural integers with the Cantor pairing function and the successor, COMPRESSED MEMBERSHIP PROBLEMS FOR REGULAR EXPRESSIONS AND HIERARCHICAL AUTOMATA, Non-primitive recursive decidability of products of modal logics with expanding domains, DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS, Double-exponential inseparability of Robinson subsystem Q₊, Canonical Models and the Complexity of Modal Team Logic, Sorting, linear time and the satisfiability problem, Automatic Structures of Bounded Degree Revisited, Model Checking FO(R) over One-Counter Processes and beyond, LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE, Algebras for querying text regions: Expressive power and optimization, Automatic structures of bounded degree revisited, Succinctness as a source of complexity in logical formalisms, Simple sentences that are hard to decide

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
• On random models of finite power and monadic logic
• Nonconvergence, undecidability, and intractability in asymptotic problems
• The complexity of elementary algebra and geometry
• On the computational complexity of the theory of Abelian groups
• Complexity of Boolean algebras
• On time-space classes and their relation to the theory of real addition
• The complexity of logical theories
• The complexity of Presburger arithmetic with bounded quantifier alternation depth
• Elementary induction on abstract structures
• The model theory of differential fields revisited
• The polynomial-time hierarchy
• Solving diophantine problems over all residue class fields of a number field and all finite fields
• Theories of Abelian groups with predicates specifying a subgroup
• The computational complexity of logical theories
• Propositional dynamic logic of regular programs
• Decision procedures and expressiveness in the temporal logic of branching time
• The elementary theory of finite fields
• Elementary theory of abelian groups without trosion, with a predicate selecting a subgroup
• Diophantine problems over local fields. III: Decidable fields
• Turing-machines and the Entscheidungsproblem
• The first order properties of products of algebraic systems
• LOGICAL THEORIES OF ONE-PLACE FUNCTIONS ON THE SET OF NATURAL NUMBERS
• Complexity of the first-order theory of almost all finite structures
• Complexity of Subcases of Presburger Arithmetic
• Relational queries computable in polynomial time
• Classifying the computational complexity of problems
• Sentences true in all constructive models
• On the elementary theory of quadruples of vector spaces
• Alternation
• Complexity classes and theories of finite models
• The Elementary Theory of Torsionfree Abelian Groups With a Predicate Specifying a Subgroup
• Model-completeness for sheaves of structures
• Model-interpretability into trees and applications
• Undecidability of the Theory of Abelian Groups with a Subgroup
• Separating Nondeterministic Time Complexity Classes
• On Moschovakis closure ordinals
• Expanded theory of ordered Abelian groups
• On the complexity of the theories of weak direct powers
• Bounds on transfer principles for algebraically closed and complete discretely valued fields
• Presburger arithmetic with bounded quantifier alternation
• Elementary properties of ordered abelian groups
• Decidability of Second-Order Theories and Automata on Infinite Trees
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Solution of a problem of Tarski