Simple sentences that are hard to decide
From MaRDI portal
Publication:810009
DOI10.1016/0890-5401(91)90033-XzbMath0733.03031OpenAlexW2052023676MaRDI QIDQ810009
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
time complexityexponential timedomino gameslimited number of quantifier alternationsrestrictions of first-order theories
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