Arratia, A. A. and Stewart, I. A. (2003) 'A note on first-order projections and games.', Theoretical computer science., 290 (3). pp. 2085-2093.
Abstract
We show how the fact that there is a first-order projection from the problem TC (transitive closure) to some other problem $\Omega$ enables us to automatically deduce that a natural game problem, $\mathcal{LG}(\Omega)$, whose instances are labelled instances of $\Omega$, is complete for PSPACE (via log-space reductions). Our analysis is strongly dependent upon the reduction from TC to $\Omega$ being a logical projection in that it fails should the reduction be, for example, a log-space reduction or a quantifier-free first-order translation.
Item Type: | Article |
---|---|
Keywords: | Descriptive complexity, Finite model theory, Quantifier-free projections. |
Full text: | (AM) Accepted Manuscript Download PDF (185Kb) |
Status: | Peer-reviewed |
Publisher Web site: | http://dx.doi.org/10.1016/S0304-3975(02)00491-7 |
Date accepted: | No date available |
Date deposited: | 25 August 2009 |
Date of first online publication: | January 2003 |
Date first made open access: | No date available |
Save or Share this output
Export: | |
Look up in GoogleScholar |