Upper and lower bounds for first order expressibility

We continue the study of first order expressibility as a measure of complexity, introducing the new class Var &Sz[v(n),z(n)] of languages expressible with v(n) variables in sentences of size z(n). We show that when the variables are restricted to boolean values: BVar &Sz[v(n),z(n)] = ASPACE&TIME[v(n),t(n)] That is variables and size correspond precisely to alternating space and time respectively. Returning to variables ranging over an n element universe, it follows that: Var[O(1)] = ASPACE[log n] = PTIME That is the family of properties uniformly expressible with a constant number of variables is just PTIME. These results hold for languages with an ordering on the objects in question, e.g. for graphs a successor relation on the vertices. We introduce an "alternating pebbling game" to prove lower bounds on the number of variables and size needed to express properties without successor. We show, for example, that k variables are needed to express Clique(k), suggesting that this problem requires DTIME[nk].