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[n^k] (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