Languages that Capture Complexity Classes
The work
| Authors | Neil Immerman |
|---|---|
| Editors | |
| Type | article |
| Year | 1987 |
| Citekey | immerman1987languages |
Where it appeared
| Published in | SIAM Journal on Computing |
|---|---|
| Publisher | Society for Industrial & Applied Mathematics (SIAM) |
| Volume | 16 |
| Issue | 4 |
| Pages | 760--778 |
Identifiers
| DOI | 10.1137/0216051 |
|---|---|
| ISSN | 0097-5397 |
Access
| Landing page | https://doi.org/10.1137/0216051 |
|---|
From crossref.
Abstract
We present a series of operators of apparently increasing power which when added to first-order logic produce a series of languages in which exactly the properties checkable in a certain complexity class may be expressed. We thus give alternate characterizations of most important complexity classes. We also introduce reductions appropriate for our setting: first-order translations, and a restricted, quantifier free version of these called projection translations. We show that projection translations are a uniform version of Valiant’s projections, and that the usual complete problems remain complete via these very restrictive reductions.
How it got here
| How it got here | agent via crossref |
|---|---|
| Added | 2026-10-23 23:53 UTC |
| Not denied by | a person 2026-10-29 17:12 UTC |
Cite it as
@article{immerman1987languages,
title = {Languages that Capture Complexity Classes},
author = {Neil Immerman},
year = {1987},
journal = {SIAM Journal on Computing},
publisher = {Society for Industrial \& Applied Mathematics (SIAM)},
volume = {16},
number = {4},
pages = {760--778},
issn = {0097-5397},
doi = {10.1137/0216051},
}
This record lives at https://refs.drheap.org/immerman1987languages/ and will keep doing so.