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

DOI10.1016/0168-0072(90)90080-LzbMATH Open0705.03017OpenAlexW3037175162MaRDI QIDQ917543FDOQ917543

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

Recommendations

• scientific article; zbMATH DE number 8764
• scientific article
• The recognition complexity of decidable theories
• scientific article; zbMATH DE number 1163984
• scientific article; zbMATH DE number 3916179

zbMATH Keywords

inseparabilitylower bounds on the computational complexity of logical theories

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (38)

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

This page was built for publication: A uniform method for proving lower bounds on the computational complexity of logical theories

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q917543)