Complexity of the first-order theory of almost all finite structures

A first-order sentence of a relational type L is true almost everywhere if the proportion of its models among the structures of type L and cardinality m tends to 1 when m tends to ∞. It is shown that Th(L), the set of sentences (of typeL) true almost everywhere, is complete in PSPACE. Further, various upper and lower bounds of the complexity of this theory are obtained. For example, if the arity of the relation symbols of L is d ⩾ 2 and if Pr Th(L) is the set of prenex sentences of Th(L), thenPr Th(L)∈DSPACE((n/logn)d)andPr Th(L)∉NTIME(o(n/logn)d).If R is a binary relation symbol and L={R}, (Th(L) is the theory of almost all graphs), thenPr Th(L)∉NSPACE(o(n/logn)).These results are optimal modulo open problems in complexity such as NTIME(T)? DSPACE(T) and NSPACE(S) = ? DSPACE(S2)