A uniform method for proving lower bounds on the computational complexity of logical theories
From MaRDI portal
(Redirected from Publication:917543)
Recommendations
Cites work
- scientific article; zbMATH DE number 3885864 (Why is no real title available?)
- scientific article; zbMATH DE number 3813598 (Why is no real title available?)
- scientific article; zbMATH DE number 3898846 (Why is no real title available?)
- scientific article; zbMATH DE number 3922637 (Why is no real title available?)
- scientific article; zbMATH DE number 3935014 (Why is no real title available?)
- scientific article; zbMATH DE number 3952713 (Why is no real title available?)
- scientific article; zbMATH DE number 4059374 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3685448 (Why is no real title available?)
- scientific article; zbMATH DE number 3710144 (Why is no real title available?)
- scientific article; zbMATH DE number 3735784 (Why is no real title available?)
- scientific article; zbMATH DE number 3756732 (Why is no real title available?)
- scientific article; zbMATH DE number 3501006 (Why is no real title available?)
- scientific article; zbMATH DE number 3561331 (Why is no real title available?)
- scientific article; zbMATH DE number 3562520 (Why is no real title available?)
- scientific article; zbMATH DE number 3586480 (Why is no real title available?)
- scientific article; zbMATH DE number 3243872 (Why is no real title available?)
- scientific article; zbMATH DE number 3285224 (Why is no real title available?)
- scientific article; zbMATH DE number 3316934 (Why is no real title available?)
- scientific article; zbMATH DE number 3349995 (Why is no real title available?)
- scientific article; zbMATH DE number 3368555 (Why is no real title available?)
- scientific article; zbMATH DE number 3032896 (Why is no real title available?)
- scientific article; zbMATH DE number 3057871 (Why is no real title available?)
- Alternation
- Bounds on transfer principles for algebraically closed and complete discretely valued fields
- Classifying the computational complexity of problems
- Complexity classes and theories of finite models
- Complexity of Boolean algebras
- Complexity of Subcases of Presburger Arithmetic
- Complexity of the first-order theory of almost all finite structures
- Decidability of Second-Order Theories and Automata on Infinite Trees
- Decision procedures and expressiveness in the temporal logic of branching time
- Diophantine problems over local fields. III: Decidable fields
- Elementary induction on abstract structures
- Elementary properties of ordered abelian groups
- Elementary theory of abelian groups without trosion, with a predicate selecting a subgroup
- Expanded theory of ordered Abelian groups
- LOGICAL THEORIES OF ONE-PLACE FUNCTIONS ON THE SET OF NATURAL NUMBERS
- Model-completeness for sheaves of structures
- Model-interpretability into trees and applications
- Nonconvergence, undecidability, and intractability in asymptotic problems
- On Computable Numbers, with an Application to the Entscheidungsproblem
- On Moschovakis closure ordinals
- On random models of finite power and monadic logic
- On the complexity of the theories of weak direct powers
- On the computational complexity of the theory of Abelian groups
- On the elementary theory of quadruples of vector spaces
- On time-space classes and their relation to the theory of real addition
- Presburger arithmetic with bounded quantifier alternation
- Propositional dynamic logic of regular programs
- Relational queries computable in polynomial time
- Sentences true in all constructive models
- Separating Nondeterministic Time Complexity Classes
- Solution of a problem of Tarski
- Solving diophantine problems over all residue class fields of a number field and all finite fields
- The Elementary Theory of Torsionfree Abelian Groups With a Predicate Specifying a Subgroup
- The complexity of Presburger arithmetic with bounded quantifier alternation depth
- The complexity of elementary algebra and geometry
- The complexity of logical theories
- The computational complexity of logical theories
- The elementary theory of finite fields
- The first order properties of products of algebraic systems
- The model theory of differential fields revisited
- The polynomial-time hierarchy
- Theories of Abelian groups with predicates specifying a subgroup
- Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
- Turing-machines and the Entscheidungsproblem
- Undecidability of the Theory of Abelian Groups with a Subgroup
Cited in
(38)- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Non-primitive recursive decidability of products of modal logics with expanding domains
- Algorithmic uses of the Feferman-Vaught theorem
- Model-checking hierarchical structures
- First-order and counting theories ofω-automatic structures
- On iterating linear transformations over recognizable sets of integers
- Fifty years of the spectrum problem: survey and new results
- 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
- Canonical models and the complexity of modal team logic
- The most nonelementary theory
- LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE
- Inverse monoids: decidability and complexity of algebraic questions.
- Hyperfinite MV-algebras
- Nonconvergence, undecidability, and intractability in asymptotic problems
- Complexity of logical theories involving coprimality
- An improved lower bound for the elementary theories of trees
- 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
- The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
- Model Checking FO(R) over One-Counter Processes and beyond
- 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
- Compressed membership problems for regular expressions and hierarchical automata
- The recognition complexity of decidable theories
- Simple interpretations among complicated theories
- Automatic structures of bounded degree revisited
- Double-exponential inseparability of Robinson subsystem \(Q_{+}\)
- 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
- Dominoes and the complexity of subclasses of logical theories
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)
