Simple sentences that are hard to decide

AbstractIt was considered to be “typical for first order theories” that a restriction to sentences with only a limited number of quantifier alternations leads to an exponential decrease of complexity. Using domino games, which were treated in a previous paper to describe computations of alternating Turing machines, we prove that this is not always true. We present a list of theories, all of them decidable in ⌣c>0ATIME(2cn, n), for which the subclasses with bounded quantifier alternations still have alternating exponential time complexity. In particular this yields non-deterministic exponential time lower bounds for very simple prefix classes (with 2 or 3 alternations). Theories with such behaviour are the theory of Boolean algebras, the theory of polynomial rings over finite fields, the theory of idempotent rings, the theory of finite sets with inclusion, the theory of semilattices, the theory of Stone algebras, the theory of distributive p-algebras in the Lee-class Bn, and the theories of natural numbers with divisibility or coprimeness