A note on first-order projections and games

Arratia, A.A.; Stewart, I.A.

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.

Citation

Arratia, A., & Stewart, I. (2003). A note on first-order projections and games. Theoretical Computer Science, 290(3), 2085-2093. https://doi.org/10.1016/s0304-3975%2802%2900491-7

• Journal Article Type: Article
• Publication Date: Jan 1, 2003
• Deposit Date: Jun 29, 2009
• Publicly Available Date: Aug 25, 2009
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 290
• Issue: 3
• Pages: 2085-2093
• DOI: https://doi.org/10.1016/s0304-3975%2802%2900491-7
• Keywords: Descriptive complexity, Finite model theory, Quantifier-free projections.
• Public URL: https://durham-repository.worktribe.com/output/1621433
• Publisher URL: http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6V1G-47T5C4X-B-3&_cdi=5674&_user=121711&_orig=browse&_coverDate=01%2F03%2F2003&_sk=997099996&view=c&wchp=dGLbVzb-zSkWb&md5=18e079ca996a694d81fbeccd5897fb59&ie=/sdarticle.pdf