Dominoes and the complexity of subclasses of logical theories

DOI10.1016/0168-0072(89)90023-7zbMath0665.03027OpenAlexW1968015483MaRDI QIDQ1115859

Erich Grädel

Publication date: 1989

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(89)90023-7

zbMATH Keywords

dominoNP-completenesstime complexityPresburger arithmeticSkolem arithmeticcomplexity of classes of quantifier prefix bounded formulas

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Polyominoes (05B50)

Related Items (12)

Context-free commutative grammars with integer counters and resets ⋮ NP satisfiability for arrays as powers ⋮ Short Presburger Arithmetic Is Hard ⋮ Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials ⋮ Circuit satisfiability and constraint satisfaction around Skolem arithmetic ⋮ Emptiness problems for integer circuits ⋮ Undecidability results on two-variable logics ⋮ On the Restraining Power of Guards ⋮ Decidable subsets of open logic and an algorithm for R-calculus ⋮ Sentences over integral domains and their computational complexities ⋮ Emptiness Problems for Integer Circuits ⋮ Simple sentences that are hard to decide

Cites Work

• A uniform method for proving lower bounds on the computational complexity of logical theories
• Real addition and the polynomial hierarchy
• Subclasses of Presburger arithmetic and the polynomial-time hierarchy
• Complexity of Boolean algebras
• The complexity of logical theories
• The complexity of Presburger arithmetic with bounded quantifier alternation depth
• Komplexität von Entscheidungsproblemen. Ein Seminar
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• The computational complexity of logical theories
• Undecidability and nonperiodicity for tilings of the plane
• The first order properties of products of algebraic systems
• ENTSCHEIDUNGSPROBLEM REDUCED TO THE AEA CASE
• Complexity of Subcases of Presburger Arithmetic
• Alternation
• Every Prime Has a Succinct Certificate
• The decision problem for standard classes
• Separating Nondeterministic Time Complexity Classes
• A Bound on Solutions of Linear Integer Equalities and Inequalities
• Presburger arithmetic with bounded quantifier alternation
• The undecidability of the domino problem
• On direct products of theories
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Dominoes and the complexity of subclasses of logical theories