Descriptive Complexity of Finite Structures: Saving the Quantifier Rank

الأصل · EN

Given a relational structure M on n elements, let D(M) be the minimum quantifier rank of a first order formula identifying M up to isomorphism in the class of n-element structures. The obvious upper bound is D(M)≤ n. We show that if the relations in M have arity at most k, then D(M)<(1-1/2k)n+k²-k+2. The coefficient at n, which equals 1-1/2k, is probably not best possible but this is the first known bound having it strictly below 1 (for fixed k). If one is content to have the worse coefficient 1-1/2k²+2, then one can choose an identifying formula of a very special form: a prenex formula with at most one quantifier alternation. A few other results in this vein are presented.