DSPACE (n/sup k/)=VAR(k+1)
The work
| Authors | Neil Immerman |
|---|---|
| Editors | |
| Type | misc |
| Year | 2002 |
| Citekey | immerman2002dspace |
Where it appeared
| Published in | Structure in Complexity Theory Annual Conference |
|---|---|
| Volume | 41 |
| Pages | 334--340 |
Identifiers
| DOI | 10.1109/sct.1991.160278 |
|---|---|
| OpenAlex | W1515777348 |
Access
| Landing page | https://doi.org/10.1109/sct.1991.160278 |
|---|
From OpenAlex, which stores abstracts as an index of words and their positions: what is shown is rebuilt from that, and reads fluently whether or not it is what the author wrote.
Abstract
The author proves that the set of properties checkable by a Turing machine in DSPACE(n/sup k/) is exactly equal to the set of properties describable by a uniform sequence of first-order sentences using at most k+1 distinct variables. He proves that this 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)). The author suggests some directions for exploiting this result to derive tradeoffs between the number of variables and the quantifier-depth in descriptive complexity. This has applications to parallel complexity.>
How it got here
| How it got here | agent via openalex |
|---|---|
| Added | 2026-10-23 23:53 UTC |
| Not denied by | a person 2026-10-29 17:12 UTC |
Cite it as
@misc{immerman2002dspace,
title = {DSPACE (n/sup k/)=VAR(k+1)},
author = {Neil Immerman},
year = {2002},
journal = {Structure in Complexity Theory Annual Conference},
volume = {41},
pages = {334--340},
doi = {10.1109/sct.1991.160278},
}
This record lives at https://refs.drheap.org/immerman2002dspace/ and will keep doing so.