The Fluted Fragment Revisited

We study the fluted fragment, a decidable fragment of first-order logic with an unbounded number of variables, originating in the work of W.V. Quine. We show that the satisfiability problem for this fragment has non-elementary complexity, thus refuting an earlier published claim by W.C. Purdy that it is in NExpTime. More precisely, we consider FL^m, the intersection of the fluted fragment and the m-variable fragment of first-order logic, for all m ≥ 1. We show that, for m ≥ 2, this sub-fragment forces m/2-tuply exponentially large models, and that its satisfiability problem is m/2-NExpTime-hard. We further establish that, for m ≥ 3, any satisfiable FL^m-formula has a model of at most (m-2)-tuply exponential size, whence the satisfiability (= finite satisfiability) problem for this fragment is in (m-2)-NExpTime. Together with other, known, complexity results, this provides tight complexity bounds for FL^m for all m ≤4.