N. Immerman, J. Buss, and D.M. Barrington, Number of Variables Is Equivalent To Space, Journal of Symbolic Logic 66(3) (2001), 1217 - 1230.

Abstract: We prove that the set of properties describable by a uniform sequence of first-order sentences using at most k+1 distinct variables is exactly equal to the set of properties checkable by a Turing machine in DSPACE[nk] (where n is the size of the universe). This set is also equal to the set of properties describable using an iterative definition for a finite set of relations of arity k. This is a refinement of the theorem PSPACE = VAR[O(1)], [Imm82]. We suggest some directions for exploiting this result to derive trade-offs between the number of variables and the quantifier depth in descriptive complexity.

Recent Publications of Neil Immerman