Simple sentences that are hard to decide

DOI10.1016/0890-5401(91)90033-XzbMath0733.03031OpenAlexW2052023676MaRDI QIDQ810009

Erich Grädel

Publication date: 1991

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(91)90033-x

zbMATH Keywords

time complexityexponential timedomino gameslimited number of quantifier alternationsrestrictions of first-order theories

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Cites Work

• Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
• A uniform method for proving lower bounds on the computational complexity of logical theories
• Real addition and the polynomial hierarchy
• Dominoes and the complexity of subclasses of logical theories
• Complexity of Boolean algebras
• The complexity of Presburger arithmetic with bounded quantifier alternation depth
• The polynomial-time hierarchy
• Domino-tiling games
• Complexity of Subcases of Presburger Arithmetic
• Domino Games and Complexity
• Presburger arithmetic with bounded quantifier alternation
• The undecidability of the domino problem
• Unnamed Item
• Unnamed Item

This page was built for publication: Simple sentences that are hard to decide