Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-17T23:11:28.310Z Has data issue: false hasContentIssue false

Number of variables is equivalent to space

Published online by Cambridge University Press:  12 March 2014

Neil Immerman
Affiliation:
Department of Computer Science, University of Massachusetts, Amherst, Massachusetts 01003, USA, E-mail: immerman@cs.umass.edu
Jonathan F. Buss
Affiliation:
Department of Computer Science, University of Waterloo, Waterloo, Ontario N2L3G1, Canada, E-mail: jfbuss@math.uwaterloo.ca
David A. Mix Barrington
Affiliation:
Department of Computer Science, University of Massachusetts, Amherst, Massachusetts 01003, USA, E-mail: barring@cs.umass.edu

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]] [8]. We suggest some directions for exploiting this result to derive trade-offs between the number of variables and the quantifier depth in descriptive complexity.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable